好好学算法之前缀和经验总结
站长
· 阅读数 28
总结
做了十几道题后，发现在前缀和的题，要么就单纯得构建一个前缀和数组， 要么就是一个表示总和的sum变量跟一个哈希表。
238. 除自身以外数组的乘积
这道题的关键是先求得前缀乘数组跟后缀乘数组，然后就可以利用当前元素的前缀乘跟后缀乘得到answer数组了。
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
let pre = [nums[0]];
let last = [];
last[nums.length -1] = nums[nums.length-1];
for(let i = 1; i < nums.length; i++) {
pre[i] = pre[i-1] * nums[i];
}
for(let i = nums.length - 2; i >= 0; i--) {
last[i] = last[i+1] * nums[i];
}
let answer = [];
answer[0] = last[1];
answer[nums.length-1] = pre[nums.length-2];
for(let i = 1; i < nums.length - 1; i++) {
answer[i] = pre[i-1] * last[i+1];
}
return answer;
};
303. 区域和检索 - 数组不可变
这道题的关键在初始化对象时，就生成前缀和。
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
let sum = [];
sum[-1] = 0;
for(let i = 0; i < nums.length; i++){
sum[i] = sum[i-1] + nums[i]
}
this.sum = sum;
};
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
NumArray.prototype.sumRange = function(left, right) {
return this.sum[right] - this.sum[left - 1];
};
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(left,right)
*/
304. 二维区域和检索 - 矩阵不可变
这道题 好像小学做的 求重合面积的。
需要注意的是，题目里说的 左上角顶点跟右下角顶点的含义，调了半天。
/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
let sum = new Array(matrix.length + 1).fill(0).map(() => new Array(matrix[0].length +1).fill(0));
for(let i = 0; i < matrix.length; i++) {
for(let j = 0; j < matrix[0].length; j++){
sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + matrix[i][j]
}
}
this.sum = sum;
};
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
return this.sum[row2+1][col2+1] - this.sum[row2+1][col1] - this.sum[row1][col2+1] + this.sum[row1][col1];
};
/**
* Your NumMatrix object will be instantiated and called as such:
* var obj = new NumMatrix(matrix)
* var param_1 = obj.sumRegion(row1,col1,row2,col2)
*/
523. 连续的子数组和
这道题的关键在于知道两个前缀和之间的关系。例如前缀和sum[i] 和前缀和sum[j] 的关系为 (sum[i] - sum[j])%k = 0;,
即sum[i]%k = sum[j]%k;
所以遍历时可以用一个哈希表来存储当前前缀和的余数。
需要注意，只能用Map，不能用字面量对象let map = {}的形式，因为map[i] === 0时，会被判断为否。
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkSubarraySum = function(nums, k) {
let map = new Map();
map.set(0, -1);
// (sum1 - sum2) % k = 0 -> sum1 % k === sum2 %k
let sum = 0;
for(let i =0; i < nums.length; i++) {
sum += nums[i];
let remain = sum % k;
if(map.has(remain)) {
if(i - map.get(remain) >= 2) {
return true;
}
}else {
map.set(remain, i);
}
}
return false
};
525. 连续数组
这道题还是用哈希表来实现，key为当前前缀的0和1数量差。 当两个前缀的数量差相等，说明中间这段的连续子数组的 数量差为0。
/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function(nums) {
let map = new Map();
map.set(0, -1);
let zeroSum = 0;
let maxDistance = 0;
for(let i = 0; i < nums.length; i++) {
if(nums[i] === 0) {
zeroSum += 1;
}else {
zeroSum -= 1;
}
if(map.has(zeroSum)) {
distance = i - map.get(zeroSum);
maxDistance = Math.max(distance, maxDistance);
}else {
map.set(zeroSum, i);
}
}
return maxDistance;
};
560. 和为 K 的子数组
这道题的还是用哈希表的解法，哈希表的key为sum，value为 相同sum出现的次数。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let map = new Map();
map.set(0,1);
let sum = 0;
let count = 0;
for(let i = 0; i < nums.length; i++) {
sum += nums[i];
delta = sum - k;
if(map.has(delta)) {
count += map.get(delta);
}
if(map.has(sum)){
map.set(sum, map.get(sum) + 1)
}else {
map.set(sum, 1)
}
}
return count;
};
724. 寻找数组的中心下标
这道题解法跟上面那道前缀乘一样。
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let pre = [];
let last = [];
pre[-1] = 0;
last[nums.length] = 0;
for(let i = 0; i < nums.length; i++) {
pre[i] = pre[i-1] + nums[i];
last[nums.length - i -1] = last[nums.length - i] + nums[nums.length -i - 1];
}
for(let i = 0; i < nums.length; i++) {
if(pre[i-1] === last[i+1]) {
return i;
}
}
return -1;
};
930. 和相同的二元子数组
这道题怎么跟560一模一样。
/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var numSubarraysWithSum = function(nums, goal) {
let map = new Map();
map.set(0, 1);
let sum = 0;
let count = 0;
for(let i = 0; i < nums.length; i++) {
sum += nums[i];
let delta = sum - goal;
if(map.has(delta)) {
count += map.get(delta);
}
if(map.has(sum)) {
map.set(sum, map.get(sum) + 1)
}else {
map.set(sum, 1);
}
}
return count;
};
这道怎么跟523一毛一样
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraysDivByK = function(nums, k) {
let map = new Map();
map.set(0, 1);
let count = 0;
let sum = 0;
for(let i = 0; i< nums.length; i++) {
sum += nums[i];
// sum1 %k === sum2 %k
let remain = (sum % k + k) % k;
if(map.has(remain)) {
count += map.get(remain);
}
if(map.has(remain)) {
map.set(remain, map.get(remain) + 1);
}else {
map.set(remain, 1);
}
}
return count;
};
1124. 表现良好的最长时间段
这道题的关键在于先将数组转化为1 跟 -1的元素。 然后就是计算1跟-1数量的和。
在利用前缀和时，如果sum > 0说明，从0到i的子数组满足要求。
如果sum <= 0,说明map.get(sum-1) 到 i的子数组符合要求。这是为什么？举个例子，在sum[i] = -2, sum[j] = -3, 那么 sum[i] - sum[j] = 1 > 0;所以 [j...i]满足子数组要求。
/**
* @param {number[]} hours
* @return {number}
*/
var longestWPI = function(hours) {
let sum = 0;
let map = new Map();
let res = 0;
for(let i = 0; i< hours.length; i++) {
sum+= hours[i] > 8 ? 1 : -1;
if(sum > 0) {
res = i + 1;
}else {
if(map.has(sum -1)) {
res = Math.max(res, i - map.get(sum - 1));
}
if(!map.has(sum)) {
map.set(sum, i)
}
}
}
return res;
};
欢迎去我的github查看更多文章 github:github.com/Sunny-lucki…
转载自:https://juejin.cn/post/7207030843213152314