Problem description:

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:

1
2
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:

1
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?

Solution:

The idea is to use an unordered_map with current sum as index, and index in the array as value.

But to construct k might not be straightforward, so we can see this example.

1
2
3
4
5
[1, 2, 3, 4, 5, 6], k= 9
-------|
sum= 6
-------------|
      sum= 15

We want to find k=9 in the above example. When we get to 5, we can see that 15-6= 9. That is to say, if we have a current sum equals to y, and we can find a previous sum x equals to y-k, then we find a subarray that can construct k.

In the above example.y= 15, k= 9, x= 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> map; //sum, index
        int res= 0, cur_sum= 0;
        
        for(int i= 0; i< nums.size(); i++){
            cur_sum+= nums[i];
            if(cur_sum == k)
                res= i+1;
            
            if(map.find(cur_sum-k) != map.end()) //can construct a k with some part of the array
                res= max(res, i-map[cur_sum-k]); //compare current maximum result with the new one
            
            if(map.find(cur_sum) == map.end()) //can not find cur_sum in map
                map[cur_sum]= i;
        }
        return res;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$
reference:
https://goo.gl/JNXSBp