# Clean python solution, one pass

• Revised code, 84ms, thanks Stefan !

``````def maxSubArrayLen(self, nums, k):
ans, acc = 0, 0               # answer and the accumulative value of nums
mp = {0:-1}                 #key is acc value, and value is the index
for i in xrange(len(nums)):
acc += nums[i]
if acc not in mp:
mp[acc] = i
if acc-k in mp:
ans = max(ans, i-mp[acc-k])
return ans``````

• Looking for `acc+k in mp` doesn't make sense. Fortunately `mp[acc+k][-1]-i` is never positive and thus never wins against `ans`, though, so it's not wrong but only a waste of time.

And the repeated `mp[acc]+[i]` is inefficient, making this an O(n^2) solution only. Try `nums = [0] * 10000`, for example.

• Thank you for pointing out the problems! I have revised my code accordingly.
But I don't understand why the mp[acc]+[i] makes it an O(n^2) solution. which operation within the for loop takes O(n) time? Please correct me if I am wrong, but I think mp[acc]+[i] is like mp[acc].extend([i]) or mp[acc].append(i), which takes constant time (amortized).

• No, `+` isn't like `extend`, `append` or even `+=`. It creates a new list and thus takes linear time.

Again, you can easily test it. Just add `nums = [0] * 10000` as the first line and click "Run Code". It'll take about 280 ms. Then use

``````        if acc not in mp:
mp[acc] = [i]
else:
mp[acc] += [i]          <= crucial difference, using "+="
``````

instead of your original line and it'll take about 50 ms (which really is close to zero, considering that Python timing always has about 50 ms overhead here.

Or just like this:

``````>>> from timeit import timeit
>>> n = 30000
>>> timeit('x += [1]', 'x = []', number=n)
0.010766158699491135
>>> timeit('x = x + [1]', 'x = []', number=n)
4.195992967101765
``````

• Thank you for kindly explaining this!

I never thought arr += [x] and arr = arr + [x] can have such huge difference..

• I created a custom test case, this solution gives answer 0, expect answer 10 (exclude 3+5, or exclude 1+7).
[1,0,2,0,3,4,7,5,6,1,9,22]
52
Do I misunderstand somthing?

• I tried your test case and it showed that the expected answer is 0, not 10. I think u misunderstood the concept of subarray, which is a consecutive part of the input array. In your example, you cannot exclude 3+5 or 1+7 since your resulting "subarray" would not be consecutive.

• Hi, cbmbbz
Can you explain how the code after second if clause works in your revised code? Thanks.

• “if acc-k in mp:” is to find whether there's a subarray with sum of k; and mp[acc-k] has the starting index of that subarry, and thus i-mp[acc-k] is the length of the subarray.

• Nice!
Do you know the difference between append and +=?

• why do you choose mp = {0:-1}