当前位置：首页 > ds >正文

力扣前缀和

ds 2025/7/13 18:30:37

这一类题，给我的感觉就是，简单的非常简单，难的又非常难

523-continuous-subarray-sum.py

    def checkSubarraySum(self, nums: List[int], k: int) -> bool:if len(nums) == 1:return FalseprefixSum = [0] * (len(nums) + 1)for i, num in enumerate(nums):prefixSum[i+1] += prefixSum[i] + num # 可以不用存，后面还会遍历的# 然后可以变成求两数和，用哈希。好像不行，因为这里是倍数关系，倍数还不能确定吧，那就遍历# 忘了长度为1的时候了# 好像有同余定理hashtable = {}for i, num in enumerate(prefixSum):key = num % kif key in hashtable:if i - hashtable[key] >= 2: # 后面减去前面的，第一次搞反了return Trueelse:hashtable[key] = ireturn False

560，hot100的题

    def subarraySum(self, nums: List[int], k: int) -> int:presuffix = [0] * (len(nums) + 1)for i, num in enumerate(nums):presuffix[i+1] = presuffix[i] + num# 还可以用这个hashtable = {}res = 0# num会混淆，改成dig# problemkey 稍微改一下，如果b-a=0,c-b=0那么c-a也得是0。所以它要记下次数for i,dig in enumerate(presuffix):if dig - k in hashtable:res += hashtable[dig - k]# 保存这个数和对应的下标hashtable[dig] = 1 if dig not in hashtable else hashtable[dig] + 1return res

974-subarray-sums-divisible-by-k.py

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

模K状态前缀和，2025年4月17日星期四

    # nums = [4,5,0,-2,-3,1]以-3为例子，到-3前缀和是4，前面同样为4的有4、45、450-2-3，所以可以res += modCount[c]def subarraysDivByK_optimize(self, nums: List[int], k: int) -> int:res = 0modCount = [0] * (k + 1) modCount[0] = 1prefixSum = 0for i, num in enumerate(nums):prefixSum += num# 好像这里不能余数的累加。可以的！c = prefixSum % kres += modCount[c]modCount[c] += 1return res