前语
剑指 Offer II 011. 0 和 1 个数相同的子数组
给定一个二进制数组 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
知识点： 数组 哈希表 前缀和
方法一：前缀和 + 哈希表
把输入数组中一切的0都替换成-1，那么题目就变成求包括相同数目的-1和1的最长子数组的长度。在一个只包括数字1和-1的数组中，假如子数组中-1和1的数目相同，那么子数组的一切数字之和就是0，因而这个题目就变成求数字之和为0的最长子数组的长度。010题求和为 k ****的接连子数组的个数，本题求最大值，稍作修正即可。
算法过程：
创建一个哈希表，用 key 来贮存 counter 值, value 来贮存当时 index。
假定碰到0就将 counter decrement (减一), 碰到1则increment (加一)。
假如能在哈希表中找到当时的 counter 值, 则取出对应的 pos, 在看 prevIndex – pos 是否比 maxLength 大, 取其间的最优解。
核心：因为以上碰1加一，碰0减一的操作，当0与1数量一致时(接连数组), 其接连数组的和为零。因而咱们知道数组前面的 counter 值是什么，在抵达该接连数组尾部时就不会变。因而咱们只需要检查哈希表中是否存在其相同的 counter 值即可！
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function(nums) {
let maxLength = 0;
const mp = new Map();
let counter = 0;
mp.set(counter, -1);
const n = nums.length;
for (let i = 0; i < n; i++) {
const num = nums[i];
if(num === 1) {
counter++;
} else {
counter--;
}
if(mp.has(counter)) {
const prevIndex = mp.get(counter);
maxLength = Math.max(maxLength, i - prevIndex);
} else {
mp.set(counter, i);
}
}
return maxLength;
};
复杂度分析
- 时刻复杂度：O(n)，其间 n 是数组 nums 的长度。需要遍历数组一次。
- 空间复杂度：O(n)，其间 n 是数组 nums 的长度。空间复杂度首要取决于哈希表，哈希表中存储的不同的 counter 的值不超过 n 个。
剑指 Offer II 012. 左右两边子数组的和持平
给你一个整数数组 nums ，请核算数组的 中心下标 ****。
数组 ****中心下标 ****是数组的一个下标，其左面一切元素相加的和等于右侧一切元素相加的和。
假如中心下标坐落数组最左端，那么左面数之和视为 0 ，因为在下标的左面不存在元素。这一点对于中心下标坐落数组最右端相同适用。
假如数组有多个中心下标，应该回来 最靠近左面 的那一个。假如数组不存在中心下标，回来 -1 。
难度：简单
示例 1：
输入：nums = [1,7,3,6,5,6] 输出：3 解说： 中心下标是 3 。 左面数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者持平。
示例 2：
输入：nums = [1, 2, 3] 输出：-1 解说： 数组中不存在满意此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1] 输出：0 解说： 中心下标是 0 。 左面数之和 sum = 0 ，（下标 0 左面不存在元素）， 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
● 1 <= nums.length <= 104
● -1000 <= nums[i] <= 1000
知识点： 数组 前缀和
方法一：遍历
假定自始至终扫描数组中的每个数字。当扫描到第i个数字时，它左面的子数组的数字之和就是从第1个数字开端累加到第i-1个数字的和。此刻它右边的子数组的数字之和就是从第i+1个数字开端累加到最后一个数字的和，这个和等于数组中一切数字之和减去从第1个数字累加到第i个数字的和。
假如从数组的第1个数字开端扫描并逐一累加扫描到的数字，当扫描到第i个数字的时候，就可以知道累加到第i个数字的和，这个和减去第i个数字就是累加到第i-1个数字的和。同时，要知道数组中的一切数字之和，只需要自始至终扫描一次数组就可以。
算法过程：
设索引 i 对应变量「左面元素相加和 sum_left 」和「右侧元素相加和 sum_right 」。
遍历数组 nums ，每轮更新 sum_left 和 sum_right 。
遍历中，遇到满意 sum_left == sum_right 时，阐明当时索引为中心下标，回来即可。
若遍历完结，仍未找到「中心下标」，则回来 -1 。
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let sumRight = 0;
let len = nums.length;
// 求和
for (let i = 0; i < len; i++) {
sumRight += nums[i];
}
let sumLeft = 0;
for (let i = 0; i < len; i++) {
sumRight -= nums[i];
if(sumLeft === sumRight) {
return i;
}
sumLeft += nums[i]
}
return -1;
};
复杂度分析
- 时刻复杂度 O(N) ： 其间 N 为数组 nums 长度。求和操作运用 O(N) 线性时刻，遍历 nums 最差运用 O(N) 线性时刻。
- 空间复杂度 O(1) ： 变量 sum_left , sum_right 运用常数大小空间。
so
- 结尾依旧：长风破浪会有时，直挂云帆济沧海！
- 在线整理的的确很好，对的文章进行了一个汇总整理，在线刷题攻略，拿走不谢，要学会站在他人的肩膀上提升自己点击这里–> 前端进阶攻略
传送门
- 简历包装 || 简历造假 vs 布景查询
- 卷王的2021总结
- 我为什么喜爱手抄代码
- 前端三年：小白变成老油条
- 今年面试了100+的前端同学我的总结
- 我为什么坚持六点起床
- 我读技术书很焦虑，读不下去书怎么办？
- 勤奋努力 === “卷” ？
- vite + react + ts 手摸手做项目系列一 （项目装备篇）
- vite + react + ts 手摸手做项目系列二 （实战篇）
