和为k的子数组

和为k的子数组 (opens new window):

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

暴力解法

暴力循环找到所有的子数组，统计子数组和等于k的子数组的数量。本题中子数组的定义必须是原数组中的连续子序列。

function subarraySum(nums, k) {
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            let sum = 0
            for (let m = i; m <= j; m++) {
                sum += nums[m]
            }
            if (sum === k) count++
        } 
    }
    return count
}

哈希表和前缀和

前缀和：数组从第一项开始到当前项的所有数的和。

根据前缀和这个概念我们可以得到，数组的当前项的值等于当前项的前缀和减去前一项的前缀和。nums[i] = prefixSum[i] - prefixSum[i - 1]。那么再推广一下这个概念，数组中从第i项到第j项的和等于什么？根据上面的公式可以简单类推，nums[i] + nums[j] = prefixSum[j] - prefix[i - 1]。借由这个公式，我们将子数组的和转换为了前缀和数组中对应两项的差值。问题就变成了，在前缀和数组中找打两项的差值刚好等于目标值。

但是实际上，我们并不需要求出前缀和数组，因为我们不关心哪两项的差值等于k，我们只关心等于k的前缀和之差出现的次数。使用哈希表记录每一个前缀和，边存边查看，如果哈希表中刚好有key为[当前前缀和-k]，说明当前前缀和刚好满足[当前前缀和-该前缀和 ===k]，将该前缀和出现的次数加给count即可。

function subarraySum(nums, k) {
    // 初始化前缀和哈希表，前缀和为0的情况只出现过1次
    let map = {0: 1}, count = 0, prefixSum = 0
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i]
        if (map[prefixSum - k]) {
            count += map[prefixSum - k]
        }
        if (map[prefixSum]) {
            map[prefixSum]++
        } else {
            map[prefixSum] = 1
        }
    }
    return count
}