题目链接

Leetcode.525 连续数组 mid

题目描述

给定一个二进制数组 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<=1051 <= nums.length <= 10^51<=nums.length<=105
• nums[i]不是 0就是 1

解法 ： 前缀和 + 哈希表

• 把 1看作是 +1
• 把 0看作是 -1

将原问题转化为：和为 0的最长子数组的长度。

用一个哈希表 cnt记录sum出现的位置（cnt[0] = -1）。如果 sumi == sumj，那么说明 [i + 1 , j]区间和一定为 0，

我们只需要用 len来记录最大的长度即可。

时间复杂度： O(n)O(n)O(n)

C++代码：

class Solution {
public:int findMaxLength(vector& nums) {int n = nums.size();unordered_map cnt{{0,-1}};int len = 0;for(int j = 0 , s = 0;j < n;j++){s += (nums[j] == 1 ? 1 : -1);if(cnt.count(s)){int i = cnt[s];if(j - i > len) len = j - i;}else cnt[s] = j;}return len;}
};

Python代码：

class Solution:def findMaxLength(self, nums: List[int]) -> int:n = len(nums)cnt , s = {0:-1} , 0ans = 0for j in range(0,n):s = s + 1 if nums[j] == 1 else s - 1if s in cnt:ans = max(ans , j - cnt[s])else:cnt[s] = jreturn ans