LeetCode刷题系列 -- 525. 连续数组

给定一个二进制数组 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

525. 连续数组 - 力扣（Leetcode）

思路：

题目可以理解为 求一个子数组，其中 0 与 1 的个数相等。这里我们考虑用一下前缀和。
不知道怎么用前缀和的方式？
来个乾坤大挪移。。。
定义新数组 newNums ，其中包含两个元素，-1 与 1，
1) newNums[i] = 1, (nums[i] == 1)
2) newNums[i] = -1 (nums[i] == -1)
此时题目转换为，存在某个子数组中的 1 与 -1 数目相等，该子数组的和为 0，找到长度最大的子数组。
剩下的思路就与 (1条消息) LeetCode刷题系列 -- 523. 连续的子数组和_在河之洲木水的博客-CSDN博客 是一致的

c++

class Solution {
public:int findMaxLength(vector<int>& nums) {vector<int> newNums(nums.size(), 0);for(int i=0; i<nums.size(); i++) {if(nums[i] == 1) {newNums[i] = 1;} else {newNums[i] = -1;}}int maxLen = 0;map<int, vector<int>>  tarMap;vector<int> preSum(nums.size(), 0); // 前缀和 preSum[i] = nums[0] + ... + nums[i]for(int i=0; i<newNums.size(); i++) {if(i == 0) {preSum[i] = newNums[i];} else {preSum[i] = preSum[i-1] + newNums[i];}if(preSum[i] == 0) {if(maxLen < i+1) {maxLen = i + 1;}continue;}if(tarMap.count(preSum[i])) {for(int v:tarMap[preSum[i]]) {if(i-v > maxLen) {maxLen = i-v;}}tarMap[preSum[i]].push_back(i);} else {vector<int> vec;vec.push_back(i);tarMap[preSum[i]] = vec;     }}return maxLen;}
};