数组前缀和

关键

• 前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和

• 题目中有连续，就应该条件反射想到滑动窗口和前缀和

• 先写出暴力解，然后找暴力解的瓶颈， 根据瓶颈就很容易知道应该用什么数据结构和算法去优化

• 前缀和算法模板

class PrefixSum {
    // 前缀和数组
    private int[] prefix;

    /* 输入一个数组，构造前缀和 */
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < prefix.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [i, j] 的累加和 */
    public int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

303. 区域和检索 - 数组不可变 (opens new window)

// 方式一：暴力解法 直接获取left和right的元素求和

/**
 * @param {number[]} nums
 */
// var NumArray = function(nums) {
//     this.nums = nums
// };

// /**
//  * @param {number} left
//  * @param {number} right
//  * @return {number}
//  */
// NumArray.prototype.sumRange = function(left, right) {
//     let sum = 0
//     for (let i = left; i <= right; i++){
//         sum += this.nums[i]
//     }
//     return sum
// };

// 方式二： 暴力的问题是每次执行 sumRange 方法的时候都会遍历一次 所以直接在初始化的时候求出所有的结果，sumRange 的时候直接去取值就行
// nums    = [-2, 0, 3, -5, 2, -1]
// resu= [0, -2, -2, 1,-4, -2, -3]

var NumArray = function (nums) {
  this.nums = nums
  this.result = new Array(this.nums.length + 1).fill(0) // 第一个项要为0 preSum 要多一项
  for (let i = 1; i < this.result.length; i++) {
    this.result[i] = this.nums[i - 1] + this.result[i - 1] // preSum[i] = preSum[i-1] + nums[i-1]
  }
  console.log(this.result)
}

NumArray.prototype.sumRange = function (left, right) {
  return this.result[right + 1] - this.result[left]
}

304. 二维区域和检索 - 矩阵不可变 (opens new window)

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
  // 构造一个前缀和的二位矩阵
  const m = matrix.length
  const n = matrix[0].length
  const res = new Array(m + 1).fill(0).map((item) => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 计算每个矩阵 [0, 0, i, j] 的元素和
      res[i][j] = res[i - 1][j] + res[i][j - 1] + matrix[i - 1][j - 1] - res[i - 1][j - 1]
    }
  }
  this.preSum = res
}

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  const preSum = this.preSum
  return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[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)
 */