likes
comments
collection
share

好好学算法之前缀和经验总结

作者站长头像
站长
· 阅读数 27

总结

做了十几道题后,发现在前缀和的题,要么就单纯得构建一个前缀和数组, 要么就是一个表示总和的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;
};

974. 和可被 K 整除的子数组

这道怎么跟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
评论
请登录