力扣 525. 连续数组

题目说明

  • 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

  • 提示：

    • 1 <= nums.length <= 10^5
    • nums[i] 不是 0 就是 1

示例

示例 1:

1
2
3
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

1
2
3
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

示例 3:

1
2
输入: nums = [0,1,1,0,1,1,1,0]
输出: 4

笔者理解

此题是一道哈希表算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现本题和昨天的每日一题连续的子数组和有点类似，只要将题目中的0换成-1，就转化成昨天类似的前缀和+同余定理的题目了，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    /*
     * 前缀和
     * 同余定理
     */
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int result = 0;

        // 前缀和
        int sum = 0;

        // 前n项累加的和可能为1，0，-1，所以采用哈希表来记录
        HashMap<Integer, Integer> map = new HashMap();

        map.put(0, 0);

        for (int i = 0; i < n; i++) {
            // 将0视为-1
            sum += 2 * nums[i] - 1;

            // 如果这个结果已经出现过了，根据同余定理，这之间的数累加必为0，也就是-1和1的个数相同
            if (map.containsKey(sum)) {
                result = Math.max(result, i + 1 - map.get(sum));
            }
            // 否则的话，将当前位置记录一下
            // 只记录一次，保证与下一次同结果间的跨度最大
            else {
                map.put(sum, i + 1);
            }
        }

        return result;
    }
}

时间空间效率都还行，可见此解法还比较适合此题；

image.png

总结

本题是今天的每日一题，难度是为中等，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。