江门网站建设,常州市城乡建设局网站,网站怎么做二维码链接地址,网站制作评分标准给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组#xff0c;并返回该子数组的长度。示例 1:输入: nums [0,1]输出: 2说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。示例 2:输入: nums [0,1,0]输出: 2说明: [0, 1] (或 [1, 0]) 是具有相同数…给定一个二进制数组 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 105nums[i] 不是 0 就是 1525. 连续数组 - 力扣Leetcode思路题目可以理解为 求一个子数组其中 0 与 1 的个数相等。这里我们考虑用一下前缀和。不知道怎么用前缀和的方式来个乾坤大挪移。。。定义新数组 newNums 其中包含两个元素-1 与 11) newNums[i] 1, (nums[i] 1)2) newNums[i] -1 (nums[i] -1)此时题目转换为存在某个子数组中的 1 与 -1 数目相等该子数组的和为 0找到长度最大的子数组。剩下的思路就与 (1条消息) LeetCode刷题系列 -- 523. 连续的子数组和_在河之洲木水的博客-CSDN博客 是一致的cclass Solution {
public:int findMaxLength(vectorint nums) {vectorint newNums(nums.size(), 0);for(int i0; inums.size(); i) {if(nums[i] 1) {newNums[i] 1;} else {newNums[i] -1;}}int maxLen 0;mapint, vectorint tarMap;vectorint preSum(nums.size(), 0); // 前缀和 preSum[i] nums[0] ... nums[i]for(int i0; inewNums.size(); i) {if(i 0) {preSum[i] newNums[i];} else {preSum[i] preSum[i-1] newNums[i];}if(preSum[i] 0) {if(maxLen i1) {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 {vectorint vec;vec.push_back(i);tarMap[preSum[i]] vec; }}return maxLen;}
};
