lintcode 1844 · subarray sum equals to k II

https://www.lintcode.com/problem/1844/?utm_source=sc-libao-zyq

/*
find min size subarray = k
so map<presum, presum's last index>

  1 1 1 2
0 1 2 3 5

0 0
1.1 
2 2
3 3. 3- 3 = 0 ,  3 - 0 = 3
5 4.  5-3 = 2.  4 - 2 = 2
*/

time: O(n)

space: O(n)

public class Solution {
    public int subarraySumEqualsKII(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int presum = 0;
        int minSize = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            presum += nums[i];
            if (map.containsKey(presum - k)) {
                minSize = Math.min(minSize, i+1 - map.get(presum - k));
            }
            map.put(presum, i + 1);
        }
        return minSize == Integer.MAX_VALUE ? - 1 : minSize; // 可能會找不到
    }
}