325. Maximum Size Subarray Sum Equals k

When I saw this problem, my first impression is that it is similar to maximum subarray sum which can be solved by Kadane's algorithm. But this problem requires sum to be k. So, if we have sum[i] to be the sum from [0, i], the problem becomes to find all pairs of sum[i] == k or sum[i]-sum[j] == k. For sum[i] == k, the len is i+1, for sum[i]-sum[j] == k, the length is j - i. If we can save all sums before i in a hash table whose (key, value) pair is (sum, index), to get j which sum[i]-sum[j] == k, we only need to look up the hash table to see if sum[i]-k exists in it.

Note, since we scan from 0 to n, if sum[i] == k, the max length so far must be i+1. Also to avoid duplicates, we only save (sum, i) when this pair isn't existing in hash table. Why we don't have to save the pair (sum, j) later? Because we want to get the maximum size, the first pair guarantees it.

1:  class Solution {  
2:  public:  
3:    int maxSubArrayLen(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      int sum = 0, maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        sum += nums[i];  
8:        if (k == sum) maxLen = i+1;  
9:        else if (mp.find(sum-k) != mp.end()) maxLen = max(maxLen, i-mp[sum-k]);  
10:        if (mp.find(sum) == mp.end()) mp[sum] = i;  
11:      }  
12:      return maxLen;  
13:    }  
14:  };