560.和为K的子数组

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    // 暴力枚举
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === k) {
            count++
        }
        let sum = nums[i]
        for (let j = i + 1; j < nums.length; j++) {
            sum = sum + nums[j]
            if (sum === k) {
                count++
            }
        }
    }
    return count
};

// 前缀和
// 从i到j的区间sum=preSum[j]-preSum[i]
var subarraySum = function (nums, k) {
    let n = nums.length

    // 求所有的前缀和，为啥是n+1项，因为第一个数的前缀和是0
    let preSumArr = new Array(n + 1).fill(0)
    preSumArr[0] = 0 // 第一个数的前缀和是0
    for (let i = 0; i < n; i++) {
        // 注意下标
        preSumArr[i + 1] = preSumArr[i] + nums[i]
    }

    // i到j区间的sum=preSum[j]-preSum[i]
    let count = 0
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (preSumArr[j + 1] - preSumArr[i] === k) {
                count++
            }
        }
    }

    return count
}

// 前缀和+哈希表优化
var subarraySum = function(nums, k) {
    const map = new Map()
    map.set(0, 1) // 

    let preSum = 0
    let count = 0
    for(let i=0;i<nums.length;i++) {
        preSum +=nums[i]
        if(map.has(preSum-k)) {
            count += map.get(preSum-k)
        }

        if(map.has(preSum)) {
            map.set(preSum, map.get(preSum) + 1)
        } else {
            map.set(preSum, 1)
        }
    }

    return count
};