https://labuladong.online/algo/problem-set/perfix-sum/#%E8%A7%A3%E6%B3%95%E4%BB%A3%E7%A0%81-3
適用范圍：快速、頻繁地計算一個索引區間內的元素之和

303 區域和檢索：數組不可變

https://leetcode.cn/problems/range-sum-query-immutable/

class NumArray(object):def __init__(self, nums):""":type nums: List[int]"""self.preSum = [0 for _ in range(len(nums)+1)]for i in range(1, len(nums)+1):self.preSum[i] = self.preSum[i-1] + nums[i-1]def sumRange(self, left, right):""":type left: int:type right: int:rtype: int"""return self.preSum[right+1] - self.preSum[left]

525 連續數組

https://leetcode.cn/problems/contiguous-array/

class Solution(object):def findMaxLength(self, nums):""":type nums: List[int]:rtype: int"""if not nums:return 0n = len(nums)preSum = [0 for _ in range(n+1)]for i in range(1, n+1):preSum[i] = preSum[i-1] + (-1 if nums[i-1] == 0 else 1)val2idx = {}res = 0# print("preSum:", preSum)for i in range(0, n+1):# print("val2idx:", val2idx)if preSum[i] not in val2idx:val2idx[preSum[i]] = ielse:res = max(res, i - val2idx[preSum[i]])return res

523 連續的子數組和

同余性質：preSum[j] - preSum[i] = n*k -> preSum[j]%k == preSum[i]%k

class Solution(object):def checkSubarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: bool"""n = len(nums)if n < 2:return FalsepreSum = [0 for _ in range(n+1)]for i in range(1, n+1):preSum[i] = preSum[i-1] + nums[i-1]hashSet = set()for i in range(2, n+1):hashSet.add(preSum[i-2] % k)if preSum[i]%k in hashSet:return Truereturn False        

560 和為k的數組

https://leetcode.cn/problems/subarray-sum-equals-k/description/
難點：用val2idx記錄preSum[i]出現的次數

class Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""if not nums:return 0n = len(nums)preSum = [0 for _ in range(n+1)]for i in range(1, n+1):preSum[i] = preSum[i-1] + nums[i-1]val2idx = {}res = 0for i in range(0, n+1):                 if preSum[i]-k in val2idx:res += val2idx[preSum[i] - k]           val2idx[preSum[i]] = val2idx.get(preSum[i], 0) + 1            return res