560. Subarray Sum Equals K

source: https://leetcode.com/problems/subarray-sum-equals-k/

Question

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Bruteforce

暴力法比较简单，就是遍历所有子数组，筛选总数为k的。

function subarraySum(nums: number[], k: number): number {
    let ret = 0;
    for (let i = 0; i < nums.length; i++) {
        let crr = 0;
        for (let j = i; j < nums.length; j ++) {
            crr += nums[j];
            if (crr === k) {
                ret += 1;
            }
        }
    }
    return ret;
};

前缀和

推断出一个重要的等式：

• pre[i]=pre[i−1]+nums[i]
• [j..i][j..i][j..i] 这个子数组和为 k：pre[i]−pre[j−1]==k (j < i)
• pre[j−1]==pre[i]−k

用哈希表来记录前缀和等于某个值的i个数。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const map = {};
    // 初始状态，即第一个数满足k的情况
    map[0] = 1;
    let crr = 0;
    let ret = 0;
    for (let i = 0; i < nums.length; i++) {
        crr += nums[i];
        // j < i, 子数组以i结尾时，有多少个以j-1为开始的子数组可以满足pre[i]−pre[j−1]==k
        if (map[crr - k] !== undefined) {
            ret += map[crr - k];
        }
        if (map[crr] === undefined) {
            map[crr] = 0;
        }
        map[crr] += 1;
    }
    return ret;
};

总结

暴力法比较容易想出来，但是优化后的方法有比较多处的细节需要想清楚。