给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:
输入: [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意: 给定的二进制数组的长度不会超过50000。
当长度大于10000的时候就不适合用复杂度为o(n^2)
c++
class Solution {
public:int findMaxLength(vector<int>& nums) {if(nums.empty()) return 0;const int n = nums.size();vector<int> pos(2*n+1,INT_MIN);int sum = 0;int ans = 0;for(int i=0;i<nums.size();i++){sum += nums[i]?1:-1;if(sum==0){ans = i+1;}else if(pos[sum+n]!=INT_MIN){ans = max(ans, i-pos[sum+n]);}else{pos[sum+n] = i;}}return ans;}
};
python3
class Solution:def findMaxLength(self, nums: List[int]) -> int:dic ={}sum = 0ans = 0for i,num in enumerate(nums):if num==0: num=-1sum += numif sum==0: ans = i+1elif(sum in dic):ans = max(ans,i-dic[sum])else:dic[sum] = ireturn ans