LeetCode 525. 连续数组

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 525. 连续数组原题链接中等

作者：

wzc1995 , 2018-07-06 15:14:33 , 所有人可见 , 阅读 2272

14

2

题目描述

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

样例

输入：nums = [0,1]
输出：2
解释：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

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

限制

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

算法

(前缀和，哈希表) $O(n)$

将数组中的 0 视作 -1，则求连续相同 0 和 1 个数的子数组就是求连续和为 0 的子数组。
连续子数组的和可以用两个前缀和相减得到，故这里就是求下标差距最大的两个相等的前缀和。
使用哈希表记录前缀和及其下标。遍历时，若当前的前缀和在哈希表中出现，则更新答案；否则将其值和下标加入哈希表。
注意哈希表中需要初始化一个前缀和 0。

时间复杂度

每个数字仅遍历一次，哈希表的单次操作时间复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

需要额外的哈希表空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        unordered_map<int, int> hash;
        hash[0] = 0;
        int x = 0;
        for (int i = 1; i <= n; i++) {
            x += (nums[i - 1] == 1 ? 1 : -1);
            if (hash.find(x) != hash.end())
                ans = max(ans, i - hash[x]);
            else
                hash[x] = i;
        }
        return ans;
    }
};

3 评论

ToThink 2023-02-06 23:15

大佬好，我想请问下，y总的代码里for循环的i为何从1开始呢？谢谢

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;
        hash[0] = 0;
        int res = 0;
        for (int i = 1, one = 0, zero = 0; i <= n; i ++ ) {
            int x = nums[i - 1];
            if (x == 0) zero ++ ;
            else one ++ ;
            int s = one - zero;
            if (hash.count(s)) res = max(res, i - hash[s]);
            else hash[s] = i;
        }
        return res;
    }
};