算法---寻找和为K的子数组

560. 和为 K 的子数组 - 力扣LeetCode最直观的解法就是暴力解class Solution: def subarraySum(self, nums: List[int], k: int) - int: count 0 n len(nums) for i in range(n): current_sum 0 for j in range(i, n): current_sum nums[j] if current_sum k: count 1 return count时间复杂度为O(n^2)最适合的方法是哈希表class Solution: def subarraySum(self, nums: List[int], k: int) - int: #哈希表键为前缀和值为该前缀和出现的次数 prefix_count {0: 1} #前缀和为0出现1次 prefix_sum 0 count 0 for num in nums: prefix_sum num if prefix_sum - k in prefix_count: count prefix_count[prefix_sum - k] # 更新当前前缀和的计数 prefix_count[prefix_sum] prefix_count.get(prefix_sum, 0) 1 return count如何理解假设有前缀和AB且AB那么从 A 之后到 B 的子数组和 B - A我们想知道之前是否有某个前缀和 A 满足B-Ak也就是AB-kprefix_sum是B我们想知道之前是否有某个前缀和 A 满足B-Ak即找之前是否有前缀和等于prefix_sum-k如果有那么这个前缀和A的下一个位置到B这段子数组的和就是k有几个这样的前缀和就找到了几个符合条件的子数组。例如nums [1,2,3], k 3第一次循环prefix_sum11-3-2不在prefix_count中更新prefix_count[1] 01 1现在prefix_count{0:1, 1:1}第二次循环prefix_sum 33-30在 prefix_count 中所以count011默认出现1次更新prefix_count[3] 01 1prefix_count {0:1, 1:1, 3:1}第三次循环prefix_sum 66-33在 prefix_count中所以count 112出现一次更新prefix_count[6] 01 1prefix_count {0:1, 1:1, 3:1, 6:1}循环结束找到子数组:[3][1,2]注意相同的前缀和可能出现多次例如nums [3, 4, -3, 2, 1, -2, 3, -1], k 534734-3217这时候前缀和7出现了第二次{72}。