什么是前缀和?

什么是前缀和

前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。

什么是一维前缀和？

一维前缀和的公式：sum[i] = sum[i-1] + arr[i] ; sum是前缀和数组, arr是内容数组。拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和。

[i, j]的区间和公式: interval [i, j] = sum[j] - sum[i - 1]

和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

思路1: 使用前缀和

首先遍历数组构建前缀和数组，在拥有前缀和数组后，通过双层循环计算数组中每一个子项与之前的子项之间的区间和(子数组的和)。此时的时间复杂度为O(n^2)。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const pre = []
    let count = 0
    
    // 构建前缀和数组
    for (let i = 0; i < nums.length; i++) {
        const a = nums[i]
        const b = pre[i - 1] === undefined ? 0 : pre[i - 1]
        pre[i] = a + b
    }

    // 使用前缀和，可以快速获得区间和
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j <= i; j++) {
            // 计算区间和，查找到满足条件的区间和，count加一
            let intervalSum;
            if (j === 0) {
                intervalSum = pre[i]
            } else if (j === i) {
                intervalSum = nums[i]
            } else {
                intervalSum = pre[i] - pre[j - 1]
            }
            if (intervalSum === k) {
                count += 1
            }
        }
    }

    return count
};

思路1(优化): 使用前缀和 + 哈希

如果只使用前缀和, 时间复杂度还是太高了。无法通过全部的测试用例，会超时。下面使用哈希表降低时间复杂度。

我们之前知道区间和的公式等于k = sum[j] - sum[i - 1], 我们通过简单的移项可以得出这个公式sum[i - 1] = sum[j] - k。我们在遍历nums时，可以获得当前的前缀和，当前的前缀和减去k，可以得到我们需要找的另一个前缀和的大小，如果hash之中有记录，我们只需要获取hash中的记录，就可以知道有多少区间和等于k了。


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 var subarraySum = function(nums, k) {
    let count = 0
    let preSum = 0
    let hash = {}

    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i]
        const key = preSum - k
        if (hash[key]) {
           count += hash[key]
        }
        if (preSum === k) {
            count += 1
        }

        // 记录前缀和出现的次数
        if (!hash[preSum]) {
            hash[preSum] = 1
        } else {
            hash[preSum] += 1
        }    
    }

    return count
};

什么是二维前缀和？

什么是二维前缀和？二维前缀和其实就是二维数组的前缀和，二维前缀和的计算过程如下：

const arr = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
]

// 对于 i = 0 j = 0   preSum[0, 0] = arr[0, 0]
// 对于 i = 0         preSum[0, j] = preSum[0, j-1] + arr[0, j]
// 对于 j = 0         preSum[i, 0] = preSum[i-1, 0] + arr[i, 0]
// 其他情况  j != 0  i != 0       preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + src[i][j] - preSum[i - 1][j - 1];

const preSum = [[], [], []]

for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[0].length; j++) {
        if (i == 0 && j == 0) {
            preSum[i][j] = arr[i][j]
        } else if (i == 0) {
            preSum[i][j] = preSum[i][j - 1] + arr[i][j]
        } else if (j == 0) {
            preSum[i][j] = preSum[i - 1][j] + arr[i][j]
        } else {
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + arr[i][j] - preSum[i - 1][j - 1]
        }
    }
}
// preSum
[
    [1, 2, 3],
    [2, 4, 6],
    [3, 6, 9]
]

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

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

什么是前缀和?

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例：

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

思路

首先求得二维数组对应的二维前缀和数组。接下来看下图：

什么是前缀和?

如果想求得A顶点到B定点的区域和，我们可以使用如下的办法

sumRegion(A,B) = preSum(O,B) - preSum(O,C) - preSum(O,D) + preSum(O,E)

递推公式:

sumRegion(row2, col2, row1, col1) = preSum[row2][col2] − preSum[row2][col1−1] − preSum[row1−1][col2] + preSum[row1−1][col1−1]

我们需要额外考虑当row2，col2，row1，col1等于0时的情况，我们额外在前缀和的一条边，一条列，这样可以避免大量的边界条件判断。

什么是前缀和?

此时的公式变为了：

sumRegion(row2, col2, row1, col1) = preSum[row2 + 1][col2 + 1] − preSum[row2 + 1][col1] − preSum[row1][col2 + 1] + preSum[row1][col1]

/**
 * @param {number[][]} matrix
 */
 var NumMatrix = function(matrix) {
    // 原矩阵
    this.matrix = matrix
    // 前缀和矩阵
    this.preSum = null

    if (matrix.length === 0 || matrix[0].length === 0) {
        return
    }
    
    // 构建前缀和矩阵
    this.preSum = []
    for (let i = 0; i < this.matrix.length; i++) {
        this.preSum.push([])
    }
    for (let i = 0; i < this.matrix.length; i++) {
        for (let j = 0; j < this.matrix[0].length; j++) {
            if (i == 0 && j == 0) {
                this.preSum[i][j] = this.matrix[i][j]
            } else if (i == 0) {
                this.preSum[i][j] = this.preSum[i][j - 1] + this.matrix[i][j]
            } else if (j == 0) {
                this.preSum[i][j] = this.preSum[i - 1][j] + this.matrix[i][j]
            } else {
                this.preSum[i][j] = this.preSum[i - 1][j] + this.preSum[i][j - 1] + this.matrix[i][j] - this.preSum[i - 1][j - 1]
            }
        }
    }
    // 前缀和矩阵额外添加一行一列
    // 添加一列
    for (let i = 0; i < this.preSum.length; i++) {
        this.preSum[i].unshift(0)
    }
    // 添加一行
    this.preSum.unshift(new Array(this.preSum[0].length).fill(0))
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    if (this.preSum) {
        return this.preSum[row2 + 1][col2 + 1] + this.preSum[row1][col1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1]
    }
    return null
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */