prefix sum 前缀和数组

Maximum Size Subarray Sum Equals k

找出数组里面最长的一段数，和等于k。

这题其实是 prefix sum array + two sum，利用前缀和数组实现快速区间和查询，同时 two sum 的方法快速地位 index.

这种 prefix sum 的下标要格外小心，很容易标错。。target value 差也是，写之前多手动过几个 case 保平安。

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return 0;
        }

        int maxSize = 0;
        // 前i项sum
        // 需要最大长度，所以需要记录index
        HashMap<Integer, Integer> map = new HashMap<>();
        // 前0项的和是0
        map.put(0,0);
        int sum = 0;

        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(map.containsKey(sum - k)) {
                maxSize = Math.max(maxSize, i - map.get(sum - k) + 1);
            } 

            if(!map.containsKey(sum)) map.put(sum, i + 1);
        }

        return maxSize;
    }
}