LeetCode [325] Maximum Size Subarray Sum Equals k

325. Maximum Size Subarray Sum Equals k

Medium

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.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4 
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2 
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

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

//C++: 96ms
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums(n+1, 0);
        unordered_map<int, int> hash;//sum, index
        hash[0] = 0;
        int ret = 0;
        for(int i=1; i<=n; ++i){
            sums[i] = sums[i-1]+nums[i-1];
            if(hash.count(sums[i])==0) hash[sums[i]] = i;
            int diff = sums[i]-k;
            if(hash.count(diff)){
                ret = max(ret, i-hash[diff]);
            }
        }
        return ret;
    }
};

//Java
class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int s = 0;
        int r = 0;
        map.put(0, -1);
        for(int i=0; i<nums.length; ++i){
            s += nums[i];
            int d = s-k;
            if(map.containsKey(d)){
                int len = i-map.get(d);
                r = Math.max(r, len);
            }
            if(!map.containsKey(s))
                map.put(s, i);
        }
        return r;
    }
}