560. Subarray Sum Equals K

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

本题给我们一个数字数组 nums 以及一个目标数字 k

题目要求我们计算出数组 nums 中有多少子数组其和为 k

解题思路

算数组中的子数组和，我们需要使用到一个前缀和技巧：

sum[num[i..j]] = sum(num[0..j]) - sum(num[0..i])

白话就是，我们要计算数组中任意两个下标 i 到 j 的子数组和，我们可以用下标为 0 到 j 的子数组和减去下标为 0 到 i 的子数组和

回到这题，我们怎么做呢

我们只需要用一个 map 来保存所有出现过的前缀和及其次数

然后我们就可以用上面公式的变形找到适合的前缀和（sum[num[i..j]]就是题目要求的 k）：

sum(num[0..i]) = sum(num[0..j]) - sum[num[i..j]]

如果找到，我们就将其出现次数加到结果中即可

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    // {prefixSum: frequency}
    const freqneucyMap = new Map([[0, 1]])
    let prefixSum = 0
    let res = 0

    for (const num of nums) {
        prefixSum += num

        const difference = prefixSum - k
        if (freqneucyMap.has(difference)) {
            res += freqneucyMap.get(difference)
        }

        freqneucyMap.set(prefixSum, (freqneucyMap.get(prefixSum) || 0) + 1)
    }

    return res
};