438. 找到字符串中所有字母异位词Medium( 四 )


用ppt画了个示意图,红色的是当前遍历到的前缀和 p r e s u m,加入他之前有两个前缀和等于 p r e s u m ? k- k ?k(蓝色范围),那么很明显,就会有两个连续子数组的和为 k k k,对应图中橙色范围 。
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)preSums = collections.defaultdict(int)preSums[0] = 1presum = 0for i in range(n):presum += nums[i]# if preSums[presum - k] != 0:count += preSums[presum - k]# 利用defaultdict的特性,当presum-k不存在时,返回的是0 。这样避免了判断preSums[presum] += 1# 给前缀和为presum的个数加1return count
【438. 找到字符串中所有字母异位词Medium】