LeetCode 560. 和为 K 的子数组

◎

本节目标

用前缀和频次把每个终点的目标子数组转化为历史前缀查询。

这道题承接前缀信息与差分：元素可为负，不能依赖滑动窗口的单调性，而要统计历史前缀。

查看原题

题意与约束

统计和为 k 的连续子数组个数。子数组必须连续，且负数和零都可能出现。

朴素思路及瓶颈

枚举每个左端点，再向右扩展并累计区间和，可以检查所有连续子数组，时间复杂度为 O(n²)。瓶颈在于大量重叠区间反复累加同一批元素；既然每段区间和都能写成两个前缀和之差，就应直接查找能与当前前缀配对的历史前缀。

前缀配对

若当前位置前缀和为 prefix，一个以当前位置结尾的目标子数组对应历史前缀 prefix - k。因此映射保存“前缀和到出现次数”；frequency[0] = 1 代表空前缀。

每轮先累计 frequency[prefix - k]，再增加当前 prefix 的次数，保证只与此前位置配对。

代码实现

两份源码都一次扫描数组，并让映射只保存已经出现的前缀和频次。

C++

C++17

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> frequency{{0, 1}};
        int prefix = 0;
        int answer = 0;
        for (int num : nums) {
            prefix += num;
            answer += frequency[prefix - k];
            frequency[prefix]++;
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        frequency = {0: 1}
        prefix = 0
        answer = 0
        for num in nums:
            prefix += num
            answer += frequency.get(prefix - k, 0)
            frequency[prefix] = frequency.get(prefix, 0) + 1
        return answer

复杂度分析

时间复杂度为期望 O(n)，空间复杂度为 O(n)。

易错点

• 漏掉初始的空前缀 0。
• 先写入当前前缀，把空区间误计入答案。

模式迁移

当题目改为“和等于目标”的连续子数组计数，优先把区间和改写为两个前缀的差；映射值需要保存次数而非单个位置。