560. Subarray Sum Equals K

Problem

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

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

Note:

• The length of the array is in range [1, 20,000].
• The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
  var map = {};
  var len = nums.length;
  var sum = 0;
  var res = 0;

  map[0] = 1;

  for (var i = 0; i < len; i++) {
    sum += nums[i];
    res += (map[sum - k] || 0);
    map[sum] = (map[sum] || 0) + 1;
  }

  return res;
};

Explain:

在 i 处，map[key] 表示 0 ~ i 中和为 key 的子数组数量。

在 i 处，0 ~ i 的和为 sum，此前和为 k 的子数组个数为 map[sum - k]。

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).