[LintCode] 838. Subarray Sum Equals K

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

Example1

Input: nums = [1,1,1] and k = 2
Output: 2
Explanation:
subarray [0,1] and [1,2]

Example2

Input: nums = [2,1,-1,1,2] and k = 3
Output: 4
Explanation:
subarray [0,1], [1,4], [0,3] and [3,4]

public class Solution {
    /**
     * @param nums: a list of integer
     * @param k: an integer
     * @return: return an integer, denote the number of continuous subarrays whose sum equals to k
     */
    public int subarraySumEqualsK(int[] nums, int k) {
        // write your code here
        int[] subSum = new int[nums.length];
        subSum[0] = nums[0];
        for (int i = 1; i < subSum.length; i++) {
            subSum[i] = subSum[i - 1] + nums[i];
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < subSum.length; i++) {
            if (map.containsKey(subSum[i] - k)) {
                res += map.get(subSum[i] - k);
            }
            map.put(subSum[i], map.getOrDefault(subSum[i], 0) + 1);
        }
        return res;
    }
}