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 (Java)

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int tempSum = 0;
        int ret = 0;
        Map<Integer, Integer> sumCount = new HashMap<>();
        sumCount.put(0, 1);
        for (int i : nums) {
            tempSum += i;
            if (sumCount.containsKey(tempSum - k)) {
                ret += sumCount.get(tempSum - k);
            }
            if (sumCount.get(tempSum) != null) {
                sumCount.put(tempSum, sumCount.get(tempSum) + 1);
            } else {
                sumCount.put(tempSum, 1);
            }
        }
        return ret;
    }
}

Solution (Javascript)

/**
 * @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).