前缀和模板

给定一个数组arr（无序），其中每个元素值可为正数、负数和0，再给定一个正数k。求arr中所有连续子数组元素累加和为k的最长子数组长度。【难度：高】
示例:
输入: [2,1,-3,4,-1,2,-1,-2,4, -2,2,-2], k = 2
输出: 11
解释: 和为 2的最长连续子数组 [1,-3,4,-1,2,-1,-2,4,-2,2,-2] 。


result = 0
for i in range(len(arr)):
  s = 0
  for j in range(i, len(arr)):
     s += arr[j]
     if s == k:
	    result = max(result, j-i+1)
return result



prefix_sum = [0]*len(arr)
prefix_sum[0] = arr[0]
for i in range(1, len(arr):
  prefix_sum[i] = arr[i]+prefix_sum[i-1]

  
result = 0
for i in range(len(arr)):
  for j in range(i+1, len(arr)):
     if prefix_sum[j] - prefix_sum[i] == k:
	     result = max(result, j-i+1)
return result

  
sum(arr[i:j+1]) == sum(arr[0:j+1])-sum(arr[0:i])
2    2   
|    |
1    3
|    |
-3   0
|    |
4    4
|    |
...  ...
|    |
-2   ?



使用前缀和+hash解决，如果使用暴力解法时间复杂度是O(N^2)，使用前缀和+hash的复杂度为O(N)，空间复杂度为O(N)，参考代码：

def get_max_length(arr, k):
    if not arr:
        return 0
    prefix_sum = {0: -1}
    result, sum = 0, 0
    for i in range(len(arr)):
        sum += arr[i]
        path_sum = sum - k
        if path_sum in prefix_sum:
            result = max(result, i-prefix_sum[path_sum])
        if sum not in prefix_sum:
            prefix_sum[sum] = i
    return result