560. Subarray Sum Equals K (Medium) and Prefix Sum

Youtube 帳號 JAVAAID的一個關於PrefixSum的影片當中使用了這個例子：

a = [6, 3, -2, 4, -1, 0, -5]
A = list(itertoools.accumulate(a))
A = [6, 9, 7, 11, 10, 10, 5]

忽略首2個數字，那麼尾5個的subarray[-2, 4, -1, 0, -5]，對應的就是A[2]直到A[6]包括前後，問你總和是多少？假設A[i, j]表示subarray的總和，答案是A[2,6] = A[0,6] - A[0,1] = 5 - 9 = -4，查表相減2個數字就知道，不用針對5個數字每個計算，得到Formula: A[i,j] = A[0,j] - A[0,i-1] = A[j] - A[i-1]。由此可得，走完整個array一次之後，查詢任意大小的subarray總和，只需要將2個數字相減，不必理會subarray大小。

因此，如果邊走邊計算PrefixSum的話，從0開始數到目前的j，就可以知道目前的PrefixSum A[j]（舉例A[j] = 10，k=3），使用formula，k = A[j] - A[i-1]或者A[i-1] = A[j]-k，問題問的是這條等式出現的總次數，即是要知道過去有多少個PrefixSum的數值等於A[j]-k = 7，換句話說，要知道過去PrefixSum等於7的次數。

對於任何一個array，它的每一個Subarray都有起點i以及終點j，那麼紀錄一下有多少個起點i構造的subarrray的和是k就好了。舉例目前PrefixSum是100，k是7，那就是說如果在此之前，任何在目前終點j的subarray sum等於100-7=93的話，都是需要計算的。因此如果在此之前我們曾經紀錄過subarray sum的出現次數的話，那麼在此我們就可以知道這個需要計算的數字了。

代碼如下

answer = 0
prefixSum = 0
counts = {}
for x in nums:
    prefixSum += x
    answer += counts.get(prefixSum-k, 0)
    counts[prefixSum] = counts.get(prefixSum, 0) + 1

留意如果subarray從index 0到達某個終點j就可以產生subarray sum k的話，那麼上面代碼就會變成counts.get(0, 0)=0，錯誤變成不用計算為答案的一部分。因此要改成counts={}，表示subarray sum等於0的次數是1。

End