前綴和是一種預處理技巧,通過構建前綴和數組,可以在O(1)時間內計算任意區間的和。
原理
原數組: [a₀, a₁, a₂, …, aₙ]
前綴和: prefix[i] = a₀ + a₁ + … + aᵢ₋₁
區間和: sum(i, j) = prefix[j+1] - prefix[i]

題目：給你一個整數數組 nums 和一個整數 k ，請你統計並返回 該數組中和為 k 的子數組的個數 。
子數組是數組中元素的連續非空序列。

解題思路：要子數組求和為k，如果把整個前綴分成兩部分，自然想到哈希（小本本），子數組前面的前綴如果跟固定的子數組（和為k）組合起來為當前前綴的總和，那麼就説明這個子數組找到了。k值是固定的，只要哈希表中存在差值的記錄那麼任務就完成了。
遍歷整個數組的前綴和，然後減去k看下剩下的前綴和在我們的小本本上嗎？如果在，説明我們的子數組已經找到，那就把小本本上的數目加入到總數中；之後不管有沒有，我們也要把當前前綴和放到小本本上，為了後來者方便去用。

注意：
1、因為整個數組存在正數、負數、0，不同前綴的值可能是一致的，那就説明我們的差值在哈希表中的時候，其對應的數目也可以是多個，我們的子數組k的起點也就可以是多個，所以加和的時候要加其對應的value，而不是1
2、初始哈希表需預存{0:1}以處理首個元素符合條件的情況

# 暴力求解（只有部分通過）
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 子數組個數初始化為0
        result = 0
        for i in range(n):
            # i 直接就滿足，那就需要加入計數
            if nums[i] == k:
                result+=1
            # 目標sum = k
            sum = nums[i]
            for j in range(i+1,n):
                sum += nums[j]
                if sum == k:
                    result+=1
                elif sum > k:
                    break
        return result
# 前綴和+哈希
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 小本本存前綴和，key是前綴和，value是出現次數
        # 邊界條件：注意默認0為1，為了考慮第一個元素就等於k的情況
        prifix_count = {0:1}
        prifix_sum = 0
        count = 0
        n = len(nums)

        for num in nums:
            prifix_sum += num
            # 如果當前（前綴和 - k）的值在哈希表中存在，那就説明我們要的子數組k已經找到，其對應的value值是我們這個子數組k的不同起點的數目，也就是子數組k的數目
            if prifix_sum-k in prifix_count:
                count += prifix_count[prifix_sum-k]

            # 無論是否找到，都要把當前前綴和存到哈希表中，為後來者服務。此前綴和存在則拿到其次數再+1，不在則直接賦值為1
            prifix_count[prifix_sum] = prifix_count.get(prifix_sum,0)+1

        return count