leetcode刷题记录：前缀和

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