題目

560. Subarray Sum Equals K 給定一個整數陣列 nums 和一個整數 k，返回總和等於 k 的子陣列的總數。子陣列是陣列中元素的連續非空序列。

解題思路

子陣列由i到j總和計算:

計算子陣列nums[i:j](包含i、不包含j)的總和sum(nums, i, j)可以有兩種方式

由indexi 加到 j (包含i、不包含j)

def sum(nums, i, j):
 s = 0
 for idx in range(i,j):
     s += nums[idx]
 return s

使用preSum的概念 preSum(i) 代表陣列nums[0:i]的總合 preSum(j) 代表陣列nums[0:j]的總合 preSum(j)減去 preSum(i)就是 nums[i:j]的總合
```
def preSum(m):
 sum(nums, 0, m)
preSum(j) - preSum(i)
```

如果使用第一種方法，時間複雜度會比較差，會有許多重複的＋的計算。這邊我們採用第二種子陣列由i到j總和的技巧，當子陣列總和sum(nums[i:j])==k 表示 preSum(j) - preSum(i) = k。由於preSum(i) = preSum(j) - k，我們可以使用字典儲存在當前index j 前，每個總和出現過多少次，對於index j只需要查找dict[preSum(j)-k]就是符合sum(nums[i:j])==k i可能的個數。

實作

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        preSum = 0
        dic = {0:1}
        for num in nums:
            preSum += num
            ans += dic.get(preSum-k, 0)
            dic[preSum] = dic.get(preSum, 0) + 1
        return ans