Subarray Sum Equals K

Problem

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

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let count = 0;
    let sum = 0;
    const map = { 0: 1 };
    for (const n of nums) {
        sum += n;
        if ((sum - k) in map) {
            count += map[sum - k];
        }
        if (!(sum in map)) {
            map[sum] = 0;
        }
        map[sum]++;
    }
    return count;
};`

Let sum[i] be the total sum of all elements from nums[0] to nums[i]. Then if there exists sum[i + j] = sum and sum[i] = sum - k, there must exist a continuous subarray whose sum equals to k. More specifically, the subarray nums[i + 1:i + j] has sum of sum[i + j] - sum[i] = sum - (sum - k) = k. In addition, we must also keep track of how many times a sum has appeared in order to properly increment count. To do so, we use map, where the key is the sum and the value is the number of times said sum has appeared.

For example, if nums = [0, 0, 1], k = 1, then the sum of 0 has occurred three times before reaching 1 (two times plus the initial count of the empty array), and so count += map[0] yields the correct solution of 3 (ie. [0, 0, 1], [0, 1], [1]).

Problem​

Solution​

Problem

Solution