525.连续数组

题目

原题 525.连续数组

解题

1.未优化版本 滑动窗口思想

最先想到的是使用滑动窗口的方法，先使用 preOneCount[i] 计算 [0,i] 区间内 1 出现的次数，然后通过从大往小遍历滑动窗口 window 去检测窗口是否合法（即窗口所在的区间内部 1 和 0 的数量是否一致）

代码如下：

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] preOneCount = new int[n];
        preOneCount[0] = nums[0]==1?1:0;
        for(int i=1; i<nums.length; i++){
            preOneCount[i]=(nums[i]==1)?preOneCount[i-1]+1:preOneCount[i-1];
        }
        // window 计算
        for (int window = n; window>=1; window--){
            for (int i=0; i<=n-window; i++){
                int oneCount = preOneCount[i+window-1] - ((i>=1)?preOneCount[i-1]:0);
                int zeroCount = window-oneCount;
                if (oneCount==zeroCount){
                    return window;
                }
            }
        }
        return 0;
    }
}

2.使用 HashMap + 自定义前缀和优化

可以使用 HashMap 去优化代码，换一个角度思考问题

• 首先，前缀和并不一定是要累加 nums[i]，可以自定义累加规则
• 所以可以结合 nums 仅包含 0,1 的特性去定义一个 preSum，在遍历区间 (i, j] 的过程中，遇到 0 就对 preSum-1，否则就+1，那么如果区间 (i, j] 内部出现的 0 和 1 数量是相同的，就会存在 preSum[i]=preSum[j]
• 在计算完 preSum 之后（这个过程类似之前计算 preOneCount，都是为了下一步计算 res 进行辅助），可以考虑在遍历过程中引入 HashMap，HashMap 会暂存 Entry(preSum[i],i)，这样在遍历到 preSum[j] 的时候，如果 preSum[j]=preSum[i]，那么就可以根据 j 和 i 拿到一个区间去更新 res。
• 上述记录 Entry 到 HashMap 的时候，只需要记录 value 第一次出现的 index 位置就行，这样能够尽可能长的获得到区间。

具体代码如下:

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        int res = 0;
        // 计算 preSum，遇到 1 则 +1, 遇到 0 则 -1.
        // 从 preSum[i] 到 preSum[j] 的过程中，如果经历了相同数量的 0 和 1, 那么一定有 preSum[j]=preSum[i]
        for (int i = 1; i < n + 1; i++) {
            preSum[i] = (nums[i-1] == 1) ? preSum[i - 1] + 1 : preSum[i - 1] - 1;
        }
        // 利用 HashMap O(n) 优化遍历
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n+1; i++) {
            int sum = preSum[i];
            if (map.containsKey(sum)) {
                int leftIndex = map.get(sum);
                res = Math.max(res, i - leftIndex);
            } else {
                // 仅记录第一次出现 sum 的 idx, 这样可以保持区间最长
                map.put(sum, i);
            }

        }
        return res;
    }
}