LeetCode_前缀和_哈希表_中等_525.连续数组

「爱情、让人受尽委屈。」 2023-10-06 23:21 43阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

**提示：**  
1 <= nums.length <= 105  
nums\[i\] 不是 0 就是 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/contiguous-array

## 2.思路 ##

（1）前缀和  
常规想法是使用前缀和数组，即 preSum\[i\] 保存 nums\[0…i - 1\] 的前缀和，然后再使用两层 for 循环来遍历满足题目条件的子数组，如果符合条件，则更新 res，否则继续遍历。遍历结束后直接返回 res 即可。但是在 LeetCode 上提交时会出现“超出时间限制”的提示！**这说明该方法（时间复杂度为 O(n2)）还需优化**，具体优化方法见思路 2。

（2）前缀和 & 哈希表  
思路参考[该LeetCode用户题解][LeetCode]。

① 对思路 1 代码中初始化数组 preSum 的操作做一个改动，**使用 preSum\[i\] 来记录 nums\[0…i - 1\] 中的元素 0 和元素 1 的个数之差**：

preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);

显然，我们可以知道:  
当 preSum\[i\] > 0 时，preSum\[i\] 表示 nums\[0…i - 1\] 中 1 比 0 多的个数；  
当 preSum\[i\] < 0 时，|preSum\[i\]| 表示 nums\[0…i - 1\] 中 1 比 0 少的个数；  
当 preSum\[i\] = 0 时，nums\[0…i - 1\] 中 0 和 1 的个数相等；

② 定义哈希表 hashMap，用于存放 preSum\[i\] 及其对应的下标 i；

③ 由于符合题目条件的子数组的长度至少为 2，所以在遍历 preSum 时从下标 2 开始。在遍历过程中，**用 hashMap 保存某个子数组中 0、1 元素相差数出现的最小下标**，即下面代码中的：

if (!hashMap.containsKey(preSum[i - 2])) {
        
        hashMap.put(preSum[i - 2], i - 2);
    }

④ 同时也判断 preSum\[i\] 是否存在于 hashMap 中， 如果存在，则设之前出现的下标位置为 **preIdx = hashMap.get(preSum\[i\])**，  
那么对应的 nums\[0…preIdx - 1\] 中元素 0 和元素 1 相差的个数为 k，**例如 \[0, 1, 1, 1\]，k = 2，preIdx = 4**  
同时也可以得知 nums\[0…i - 1\] 中元素 0 和元素 1 相差的个数也为 k，**例如 \[0, 1, 1, 1, 0, 1\]，k = 2，i = 6**  
那么此时 **nums\[preIdx…i - 1\] 中元素 0 和元素 1 的个数必相等，即符合条件的子数组为 \[0, 1\]，对应的长度为 i - preIdx**，此时更新 res 即可。

推导的过程也比较简单：

由 preSum[i] = k -> nums[0...i - 1] 中元素 0 和元素 1 相差的个数为 k，
    由 preSum[preIdx] = k -> nums[0...preIdx - 1] 中元素 0 和元素 1 相差的个数为 k，且 preIdx < i
    由于 nums[0...preIdx - 1] 包含 nums[0...i - 1]，那么显然 nums[0...preIdx - 1] 中元素 0 和元素 1 个数相差为 k 的区间正好
    是 nums[0...i - 1]，所以剩余的区间 nums[preIdx...i - 1] 中元素 0 和元素 1 的个数必相等。

## 3.代码实现（Java） ##

//思路1————前缀和
    class Solution {
        
        public int findMaxLength(int[] nums) {
        
            int res = 0;
            int length = nums.length;
            int[] preSum = new int[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            for (int i = 0; i < length - 1; i++) {
        
                for (int j = i + 2; j < length + 1; j += 2) {
        
                    int sum_ij = preSum[j] - preSum[i];
                    if (sum_ij != 0 && (j - i) / sum_ij == 2 && (j - i) % sum_ij == 0) {
        
                        res = Math.max(res, j - i);
                    }
                }
            }
            return res;
        }
    }

//思路2————前缀和 & 哈希表
    class Solution {
        
        public static int findMaxLength(int[] nums) {
        
            int res = 0;
            int length = nums.length;
            int[] preSum = new int[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
            }
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 2; i <= length; i++) {
        
                if (!hashMap.containsKey(preSum[i - 2])) {
        
                    hashMap.put(preSum[i - 2], i - 2);
                }
                if (hashMap.containsKey(preSum[i])) {
        
                    int preIdx = hashMap.get(preSum[i]);
                    res = Math.max(res, i - preIdx);
                }
            }
            return res;
        }
    }

[LeetCode]: https://leetcode.cn/problems/contiguous-array/solution/gong-shui-san-xie-qian-zhui-he-ha-xi-bia-q400/