謹記： 數組不是單調的話，不要用滑動窗口，考慮用前綴和

寫法一：兩次遍歷

代碼的核心思想是通過?前綴和?和?哈希表?來高效地統計符合條件的子數組個數。具體步驟如下：

1. 計算前綴和數組?s：

   • s[i]?表示?nums?的前?i?個元素的和。
   • s[0] = 0，表示前 0 個元素的和為 0。
   • 例如，nums = [1, 1, 1]，則?s = [0, 1, 2, 3]。

2. 使用?defaultdict?記錄前綴和出現的次數：

   • defaultdict(int)?是一個字典，默認值為?0。如果訪問一個不存在的鍵，會返回?0，而不是拋出異常。
   • cnt[sj]?表示前綴和?sj?出現的次數。

3. 遍歷前綴和數組?s，統計符合條件的子數組個數：

   • 對于每個前綴和?sj，檢查是否存在前綴和?sj - k。
     • 如果存在，則說明從某個位置到當前位置的子數組和為?k。
     • 將?cnt[sj - k]?的值加到?ans?中。
   • 將當前前綴和?sj?記錄到?cnt?中。

from collections import defaultdictclass Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# 1. 計算前綴和數組 ss = [0] * (len(nums) + 1)  # s[0] = 0，表示前 0 個元素的和為 0for i, x in enumerate(nums):s[i + 1] = s[i] + x  # s[i+1] = s[i] + nums[i]# 2. 初始化結果和哈希表ans = 0  # 記錄符合條件的子數組個數cnt = defaultdict(int)  # 哈希表，記錄前綴和出現的次數# 3. 遍歷前綴和數組，統計符合條件的子數組個數for sj in s:# 如果存在 s[i] = sj - k，則說明從 i+1 到 j 的子數組和為 kans += cnt[sj - k]# 將當前前綴和 sj 記錄到哈希表中cnt[sj] += 1return ans  # 返回結果

寫法二：一次遍歷

• 前綴和：使用變量?s?動態計算當前的前綴和。
• 哈希表：使用哈希表?cnt?記錄前綴和出現的次數。
• 核心思想：對于當前前綴和?s，檢查是否存在前綴和?s - k。如果存在，則說明從某個位置到當前位置的子數組和為?k。

核心邏輯

1. 更新前綴和：
   • s += x：將當前元素?x?加到前綴和?s?中。
2. 檢查是否存在?s - k：
   • 如果?cnt[s - k]?存在，則說明從某個位置到當前位置的子數組和為?k。
   • 將?cnt[s - k]?的值加到?ans?中。
3. 記錄當前前綴和：
   • cnt[s] += 1：將當前前綴和?s?記錄到哈希表中。

from collections import defaultdictclass Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""ans = s = 0  # ans 記錄結果，s 記錄當前前綴和cnt = defaultdict(int)  # 哈希表，記錄前綴和出現的次數cnt[0] = 1  # 初始化，s[0]=0 出現了一次# 遍歷數組，動態計算前綴和for x in nums:s += x  # 更新當前前綴和# 如果存在 s - k，則說明從某個位置到當前位置的子數組和為 kans += cnt[s - k]# 將當前前綴和 s 記錄到哈希表中cnt[s] += 1return ans  # 返回結果