325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

 

//首先要理解这个题目的意思，这个题目相当于找到一个从i到j的范围，使得（nums[i]+…+nums[j]) = k, 问最大的范围是什么
//所以我们可以首先来计算每个数字的前置和，所以sum(i,j) = sum(从0到j)-sum(从0到(i-1))=k，因此对于每一个sum(j),我们只需要检查是否这里存在一个sum(i-1)=sum(j)-k 我们可以用HashMap来存储之前计算出的和
// map.get(sum-k)取出之前index到(i-1)的和为(sum-k)的index

 

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int maxLen = 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(!map.containsKey(sum)){
                map.put(sum, i);
            }
            if(map.containsKey(sum - k)){
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            }
        }
        return maxLen;
    }
}