【数组】前缀和

[miracles1919]

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

• 假设 preSum[i] 表示第 0 项到第 i 项的和
• nums[i] = preSum[i] - preSum[i - 1]
• nums[i] + ... + nums[j] = preSum[i] - preSum[i - 1] + ... + preSum[j] - preSum[j - 1] = preSum[j] - preSum[i - 1]
• sumRange(i, j) = preSum[j] - preSum[i - 1]
• 处理下边界 preSum[-1] = 0

参考：笨猪爆破组

[miracles1919]

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

时间复杂度 O(n) 空间复杂度 O(n) 查询 O(1)

/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
    const preNums = []
    const len = nums.length

    preNums[-1] = 0

    for (let i = 0; i < len; i++) {
        preNums[i] = preNums[i - 1] + nums[i]
    }

    this.nums = nums
    this.preNums = preNums
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
    return this.preNums[right] - this.preNums[left - 1]
};

[miracles1919]

剑指 Offer II 010. 和为 k 的子数组

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const n = nums.length
    const preSum = new Array(n + 1).fill(0)
    for (let i = 0; i < n; i++) {
        preSum[i + 1] = preSum[i] + nums[i]
    }
    let res = 0

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            if (preSum[i] - preSum[j - 1] === k) res++
        }
    }

    return res
};

只用前缀和会超出时间限制，进一步优化

• preSum[i] - preSum[j - 1] === k 可以转换为 preSum[j - 1] === preSum[i] - k
• 即统计存在几个 preSum[j] 等于 preSum[i] - k
• 建立哈希表，和为 key，次数为 value，记录 preSum[i] 出现的次数

时间复杂度 O(n)，空间复杂度 O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const map = new Map()
    map.set(0, 1)
    let res = 0, preSum = 0
    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i]
        if (map.has(preSum - k)) {
            res += map.get(preSum - k)
        }

        map.set(preSum, (map.get(preSum) || 0) + 1)
    }

    return res
};

参考：前缀和技巧：解决子数组问题