网站关键字 怎么设置,阿里云网站怎么建设,wordpress多站点管理,wordpress事件提醒题目#xff1a;
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组#xff0c;并返回该子数组的长度。
妈的 连题目都没有读懂#xff01;本来看成是找到两个连续子数组#xff0c;两个连续子数组的 0 1 个数分别相同#xff0c;我说怎么看着如此…题目
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。
妈的 连题目都没有读懂本来看成是找到两个连续子数组两个连续子数组的 0 1 个数分别相同我说怎么看着如此复杂。
题目转换
在一个数组里找到一个连续子数组其中0和1 的数量是一致的求最大的连续子数组的长度。
解题过程
暴力
遍历所有连续子数组的0和1 的个数如果相同则维护这个连续子数组的最大长度。
巧妙的转换
相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和 为 0
如果想要求子数组的元素和 ⇒ 计算数组的前缀和。 prefixSum[i] [0…i] 的前缀和元素的累加。 [i…k] 的元素累加和 prefixSum[k]-prefixSum[i-1] 所以相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和 为 0 ⇒ prefixSum[k]-prefixSum[i] 0 长度为 i- k ⇒ 当出现前缀和相同时维护一个最大的长度。
思路1x
维护一个prefixSum表。遍历nums用两个for循环遍历所有子数组。
思路2
用一个map记录前缀和和第一次出现的位置。key⇒value 的形式。map.has 意味着出现了前缀和一致的情况则维护最大长度。
/*** param {number[]} nums* return {number}*/
var findMaxLength function(nums) {let max 0;// 如果连续子数组索引从0开始则是priefix-prefix[-1],因此要提前保存-1但是很难想到。const map new Map();map.set(0,-1)let counter 0;for (let i 0; i nums.length; i) {if (nums[i] 0) {counter--;} else {counter;}if (map.has(counter)) {max Math.max(max, i - map.get(counter));} else {map.set(counter, i);}}return max;
}; 思路3
最长的连续子数组是以index 0 为开头的特殊情况要么使用思路二在map里添加 index -1 的情况。
要么使用思路三sum 0 的情况sum是从index 0 开始算的相当于算的就是每个以index 0 为开头的连续子数组的和。
/*** param {number[]} nums* return {number}*/
var findMaxLength function(nums) {let max 0;const map new Map();let sum 0;for (let i 0; i nums.length; i) {if (nums[i] 0) {sum --;} else {sum ;}if(sum 0){max Math.max(max,i1)}else if (map.has(sum)) {max Math.max(max, i - map.get(sum));} else {map.set(sum , i);}}return max;
};
