leetcode 560. 和为K的子数组

发表于 分类于 阅读次数：

解题思路

定义pre[i]

下标[0, i]的子数组和

求解方法

下标[j, i]的子数组和为k <=> pre[i]-pre[j-1] == k <==> pre[j-1] == pre[i]-k (注意：j <= i）
通过计算第i个元素前，有多少个pre等于pre[i]-k，可得到以第i个元素结尾的和为k的子数组个数
遍历n个元素，累加和为k的子数组个数，即可得到答案

时间复杂度

O(n)

空间复杂度

O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ret = 0
        pre_sum = 0
        pre_val_to_cnt = defaultdict(int)
        pre_val_to_cnt[0] = 1

        for i, num in enumerate(nums):
            pre_sum += num
            ret += pre_val_to_cnt.get(pre_sum - k) or 0
            pre_val_to_cnt[pre_sum] += 1

        return ret