PeterQwQ
0%

Leetcode 560 和为 K 的子数组

发表于 更新于

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中的一个连续序列。

想都没想，直接用了双指针，也是直接WA，然后才发现有负数数据。

思考了一下，这个题目实际上就是需要求解 sum(i, j) = k (i < j) 的个数，那么可以变成前缀和的问题。实际上，sum(i, j) = sum(0, j) - sum(0, i)，那么只需要求解 sum(0, i) = sum(0, j) - k 的个数即可。

那么在实际实现的过程中，可以使用一个哈希表来存储前缀和的个数，然后遍历数组，对于每一个元素，计算当前的前缀和，然后查找哈希表中是否存在 sum(0, i) - k 的前缀和，如果存在，那么就说明存在一个子数组的和为 k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hash_prefix = {}
        n = len(nums)
        ans = 0
        prefix = [0]
        for i in range(n):
            prefix.append(prefix[-1] + nums[i])

        for i in range(len(prefix)):
            ans += hash_prefix.get(prefix[i]-k, 0)
            hash_prefix[prefix[i]] = hash_prefix.get(prefix[i], 0) + 1

        return ans

这里有一些可以注意的地方，例如代码 ans += hash_prefix.get(prefix[i]-k, 0) 和 hash_prefix[prefix[i]] = hash_prefix.get(prefix[i], 0) + 1，前后不能够交换，举个简单的例子比如 nums = [2], k = 0 ，那么实际上答案是 0，但是如果交换了顺序，那么答案就会变成 1。