Problem: 560. 和为 K 的子数组
如果子数组是从start到end
那么用前缀和pre来表示的话,这个子数组的和就是pre[end] - pre[start - 1]
即:
pre[end] - pre[start - 1] == k
可以转换成:
pre[start - 1] == pre[end] - k
所以可以遍历end,pre[end] - k的值可以在O(1)时间复杂度内获得。
那题目就变成了找前面有几个pre[start - 1]。
这个可以用hash来存,所以总的时间复杂度仅为O(n)。
时间复杂度:
添加时间复杂度, 示例: O ( n ) O(n) O(n)
空间复杂度:
添加空间复杂度, 示例: O ( n ) O(n) O(n)
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
length = len(nums)
ans = 0
pre = [0] * length
pre[0] = nums[0]
for i in range(1, length):
pre[i] = pre[i - 1] + nums[i]
d = dict()
d[0] = 1
for end in range(length):
if pre[end] - k in d:
ans += d[pre[end] - k]
if pre[end] in d:
d[pre[end]] += 1
else:
d[pre[end]] = 1
return ans
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
length = len(nums)
ans = 0
pre = 0
d = dict()
d[0] = 1
for end in range(length):
pre += nums[end]
if pre - k in d:
ans += d[pre - k]
if pre in d:
d[pre] += 1
else:
d[pre] = 1
return ans