前缀和数组

303. 区域和检索 - 数组不可变

思路

前缀和：由于数组不可变，那么可以将每项和存起来

代码

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
  let sum = 0;
  this.preSum = [0];
  for(let i = 0; i < nums.length; i++) {
    this.preSum[i+1] = this.preSum[i] + nums[i];
  }
};
/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
  return this.preSum[j+1] - this.preSum[i];
};

复杂度分析

时间复杂度

• 初始化的时间复杂度为 #card=math&code=O%28N%29)
• sumRange的时间复杂度为 #card=math&code=O%281%29)

空间复杂度 #card=math&code=O%28N%29)

304. 二维区域和检索 - 矩阵不可变

思路

找规律：

1、当前的前缀和prefixSum[row][col] = prefix[row-1][col] + prefix[row][col-1] - prefix[row-1][col-1] + matrix[row][col]

2、当前矩阵块的前缀和sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1]

3、需要注意取值边界，越界取 0

代码

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
  const rowLen = matrix.length, colLen = matrix[0] && matrix[0].length;
  const prefixSum = Array(rowLen).fill(0).map(item => Array(colLen));
  for(let row = 0; row < rowLen; row ++) {
    for(let col = 0; col < colLen; col ++) {
      let prevSumRow = prefixSum[row][col-1] || 0;
      let prevSumCol = (prefixSum[row-1] && prefixSum[row-1][col]) || 0;
      let prevSumRowCol = (prefixSum[row-1] && prefixSum[row-1][col-1]) || 0;
      prefixSum[row][col] = prevSumRow + prevSumCol - prevSumRowCol +matrix[row][col]
    }
  }
  // console.log(prefixSum)
  this.prefixSum = prefixSum;
};
/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
  const sum = this.prefixSum;
  return sum[row2][col2] - ((sum[row1-1] && sum[row1-1][col2]) || 0) - (sum[row2][col1-1] || 0) + ((sum[row1-1] && sum[row1-1][col1-1]) || 0)
};
/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

复杂度分析

时间复杂度 初始化 #card=math&code=O%28N%5E2%29) sumRegion #card=math&code=O%281%29)
空间复杂度 #card=math&code=O%28N%5E2%29)

238. 除自身以外数组的乘积

思路

除自身以外数组的乘积 = 元素左区间乘积 * 元素右区间的乘积

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  const res = [], len = nums.length;
  let k = 1
  for(let i = 0; i < len; i ++) {
    res[i] = k; // 左边的乘积
    k *= nums[i]; // 存储左边的乘积
  }
  k = 1;
  for(let i = len - 1; i >= 0; i --) {
    res[i] *= k; // k为该数右边的乘积 * 当前左边的乘积
    k *= nums[i];
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)