leetcode 560 和为k 的子数组

正文

一般解法

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:number = 0for i in range(len(nums)):for j in range(i , len(nums)):if sum(nums[i:j + 1]) == k:number += 1return number

上述方法虽然可行，但是时间复杂度为 $O\left(n^2\right)$。不够迅速，因此，我们考虑使用其他方式实现。

字典方法

import collections
from typing import Listclass Solution:def subarraySum(self, nums: List[int], k: int) -> int:count = 0dict1 = collections.defaultdict(int)dict1[0] = 1pre_sum = 0for i in range(len(nums)):pre_sum += nums[i]count += dict1[pre_sum - k]dict1[pre_sum] += 1return count

需要特别注意的是，这里的 count += dict1[pre_sum - k] 和 dict1[pre_sum] += 1 位置不能互换。

如果大家觉得有用，就请点个赞吧~