560. Subarray Sum Equals K

Link

Solution

跟

1. Two Sum

2. Path Sum III

概念類似都是透過map紀錄每個歷史sum值以及出現次數

查找map中的currentSum - K出現次數， 就可以知道 以目前的currentNode結尾且sum = k的subarray次數

    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ret = 0;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
            cur += nums[i];
            ret += map.getOrDefault(cur - k, 0);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }
        
        return ret;
    }

**Complexity Analysis**

• Time complexity : O(n)O(n). The entire numsnums array is traversed only once.

• Space complexity : O(n)O(n). Hashmap map can contain upto nn distinct entries in the worst case.