LeetCode - 560. Subarray Sum Equals K

Thoughts:

I can calculate current sum and remove prefix subarray sum to find the k.

The equation will be like: current sum - prefix subarray sum = k

or I can say…

current sum - k = prefix subarray sum

But there can be multiple prefix subarray sums, so I need to store them.

The time complexity will be O(n).

Thoughts visuzlization:

k = 3
nums = [1,2,3]
prefix sum map = {0: 1} (nothing means 0)
answer = 0

[1,2,3] current sum = 1
 i      prefix subarray sum = 1 - 3 = -2
        can't find any prefix subarray sum in the map
        prefix sum map = {0: 1, 1: 1}

[1,2,3] current sum = 3
   i    prefix subarray sum = 3 - 3 = 0
        find the prefix subarray sum in the map, answer += 1
        prefix sum map = {0: 1, 1: 1, 3: 1}

[1,2,3] current sum = 3
     i  prefix subarray sum = 6 - 3 = 3
        find the prefix subarray sum in the map, answer += 1
        prefix sum map = {0: 1, 1: 1, 2: 1, 3: 1, 6: 1}

so answer is 2

Code:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let sum = 0;
  let count = 0;
  const map = new Map();
  map.set(0, 1);
  for (let num of nums) {
    sum += num;
    const cut = sum - k;
    if (map.has(cut)) count += map.get(cut);
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
};

Reference

Original link

Basic prefix sum