• 求解連續子數組的和的問題，常常會使用到這個前綴和的思路，當然當數組存在單調性的時候，可以考慮使用不定長滑動窗口，在這里解釋一下，何為數組的和存在這個單調性？就是nums[i]>=0或者nums[i]<=0,就是最終這個窗口的和值是隨著窗口的大小變大而窗口的和值是隨著變大或者變小的
• 當然，前綴和更能處理這種非單調性的問題，當出現子數組的和的某種性質的統計或者判斷的時候，我們常常會使用到哈希表進行對應的存儲

930.和相同的二元子數組

930.和相同的二元子數組

• 這個題目有多種解法，由于存在這個nums[i]>=0,所以是存在這個單調性的問題，所以考慮使用滑動窗口，當然，由于這個是恰好型的問題，所以考慮使用兩個至少型的計算進行轉化

class Solution:# 定義嵌套方法，并不使用 self參數def numSub(self,nums:List[int],goal:int ) ->int :left = count = ans = 0for right,i in enumerate(nums):count+=iwhile count >= goal and left <= right:count-=nums[left]left+=1ans += leftreturn ansdef numSubarraysWithSum(self, nums: List[int], goal: int) -> int:# 打算使用越長越好的方法，求解出和 >= goal 和 >= goal+1的情況return self.numSub(nums,goal) - self.numSub(nums,goal+1)

• 更加通用的方法是，使用這個前綴和+哈希表，對于子數組的和為goal,我們只需使用哈希表存儲對應的前綴和的次數，對于子數組的和為goal,只需查詢當前的cusum-goal是否存在哈希表中，如果存在，則加上對應的次數，最后再更新這個前綴出現的次數即可

from collections import defaultdict
class Solution:def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:n = len(nums)# 子數組要求是和為goal的子數組的數目，我們只需不斷累加，記錄對應的累加和的出現次數cursum = 0store = defaultdict(int)store[0] += 1ans = 0for i,c in enumerate(nums):cursum += c if cursum - goal in store:ans += store[cursum-goal]store[cursum]+=1return ans

523.連續的子數組和

523.連續的子數組和

• 倍數的問題，就不是單純存儲這個前綴和的出現的次數了，仔細想想，得存儲這個%k的余數的情況，因為兩個同余數的前綴和作差，那么該子數組的和肯定是k的倍數，由于考慮的是長度問題，所以哈希表記錄的是余數出現的位置的下標

class Solution:def checkSubarraySum(self, nums: List[int], k: int) -> bool:# 字典用于存儲余數及其對應的索引，初始化為 {0: -1} 以處理從索引0開始的子數組remainder_dict = {0: -1}cumulative_sum = 0  # 累加和# 遍歷數組中的每個元素for i, num in enumerate(nums):cumulative_sum += num  # 更新累加和rem = cumulative_sum % k  # 計算當前累加和對k的余數# 如果余數已經存在于字典中if rem in remainder_dict:# 檢查當前子數組的長度是否至少為2if i - remainder_dict[rem] >= 2:return Trueelse:# 如果余數不存在，則記錄當前余數對應的索引remainder_dict[rem] = i# 如果沒有找到符合條件的子數組，返回Falsereturn False