字首和模闆

給定一個數組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