// O(n) complexity.
// Core idea: for the same cumulative sum value, we
// only keep it's first appearance, so at last the
// subarray is guaranteed to be the longest.
// Also, note the brilliant idea of using the sum value
// as the key of the map.
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> m;
m[0] = 1;
int sum = 0;
int maxLen = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (!m.count(sum)) m[sum] = i;
if (m.count(sum  k)) maxLen = max(maxLen, i  m[sum  k]);
}
return maxLen;
}
C++ easy understand solution with comment


@machuiwen said in C++ easy understand solution with comment:
ray is guaranteed
why we need m[0]=1?

@nguyenton68 The 1 at
m[0]=1
is just a virtual index. For example, in the array[2, 1, 2, 1]
andk=1
. We know that1+2==1
. Therefore, whose index are1
and2
. But on unordered_map m, their index are actually0
and2
. The value on the left has a1
in it. That's why we need to setm[0]
to be1
to suit for the case where we started counting from the very beginning.