LeetCode LCR 010. 和为 K 的子数组

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 010. 和为 K 的子数组

题意分析

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

要的是个数而不是具体位置，说明可以按某个维度批量累加；「连续」限定了候选是 $O(n^2)$ 个区间而非 $2^n$ 个子集。数据规模 $n \le 2 \times 10^4$，$O(n^2)$ 约 $4 \times 10^8$ 次操作，在时限上非常危险，目标应当是 $O(n)$。

决定性的约束是元素可以为负、可以为零。这一条直接判掉滑动窗口：区间和不再随窗口扩张单调递增，「和超了就收缩左端」的判据完全失效。剩下的通用工具就只有前缀和——它把「区间和」翻译成「两个前缀和之差」，从而把「找区间」变成「找配对」。

一旦转成配对问题，元素可负这件事反而不再是障碍：我们要找的是「之前出现过多少个前缀和恰好等于当前前缀和减 k」，这是一个纯粹的计数查询，与元素正负无关。

边界要留意三处：整个数组的和恰好等于 k 时，对应的左端点是数组开头，需要一个「空前缀」参与配对；k 可以是 $0$ 甚至负数，所以不能对 k 的符号做任何假设；同一个前缀和值可能出现多次（比如数组中有 $0$ 或正负抵消），因此哈希表必须记出现次数而不是「是否出现过」。

解法：前缀和维护区间信息

核心思路

暴力做法是枚举左右端点，或者固定左端点向右累加，$O(n^2)$。瓶颈在于：对每个右端点，我们都在从头把所有左端点重新试一遍，而这些左端点的信息其实早就可以整理好。

第一步是引入前缀和：令 $s_j = nums[0] + \dots + nums[j]$，并约定 $s_{-1} = 0$。那么子数组 nums[i..j] 的和就是 $s_j - s_{i-1}$。于是「和为 k 的子数组」等价于「一对下标 $(i-1, j)$ 满足 $s_j - s_{i-1} = k$」，也就是 $s_{i-1} = s_j - k$。

第二步是把配对查询做成 $O(1)$：固定右端点 j，答案的增量就是「在 j 之前出现过多少个前缀和等于 $s_j - k$」。用一个哈希表边扫边记录每个前缀和值出现的次数，查询就是一次 get。这样每个右端点只做常数工作，整体降到 $O(n)$。

要维护的状态和不变量是：s 是当前已扫描元素的前缀和；cnt 中记录的是所有「严格位于当前元素之前」的前缀和（含空前缀 $s_{-1} = 0$）各自出现的次数。这条「严格之前」是全部正确性的关键，它由代码里的顺序保证——先查询 cnt[s - k]，再把当前的 s 写入 cnt。顺序反过来的话，当 k == 0 时当前前缀和会和自己配对，凭空多出 $n$ 个长度为零的「子数组」。

cnt 的初始化 cnt[0] = 1 代表的正是那个空前缀 $s_{-1} = 0$。它让「从下标 $0$ 开始的子数组」也能被正常配对：若 $s_j = k$，则需要找一个值为 $0$ 的前缀和，而这个 $0$ 只能来自空前缀。

解题步骤

初始化 cnt = {0: 1}。这一项代表空前缀，缺了它，所有以下标 $0$ 为左端的答案都会丢失。计数值是 $1$ 而不是 $0$，因为空前缀确实「出现过一次」。

s = 0、answer = 0，然后顺序遍历数组。只需要一遍扫描，不需要预先构造完整的前缀和数组——s 本身就是滚动的前缀和。

每步先 s += x 更新前缀和。此时 s 的语义是「以当前元素为右端点的前缀和」。

再 answer += cnt.getOrDefault(s - k, 0)。查的是「有多少个更早的前缀和等于 s - k」，每一个这样的前缀和都对应一个和为 k 的子数组，所以是把计数值整体加进去，而不是加 $1$。

最后才把 s 记入 cnt。查询在前、写入在后，保证配对的左端点严格早于当前右端点。这一行的顺序是本题最容易写反、也最容易被面试官追问的地方。

用「累加计数」而不是「记录下标」。本题只要个数，同一个前缀和值出现多次时每一次都能贡献一个答案，所以存次数；如果题目改成求最长子数组（325、LCR 011），才需要改成存最早出现的下标。

循环结束返回 answer，无需后处理。

以 nums = [1, 2, 3]、k = 3 走一遍，期望答案 2。初始 cnt = {0: 1}、s = 0、answer = 0。第一个元素 $1$：s = 1，查 cnt[1 - 3] = cnt[-2] = 0，答案不增；写入后 cnt = {0: 1, 1: 1}。第二个元素 $2$：s = 3，查 cnt[3 - 3] = cnt[0] = 1，answer = 1——这个 $1$ 来自空前缀，对应的子数组是 [1, 2]；写入后 cnt = {0: 1, 1: 1, 3: 1}。第三个元素 $3$：s = 6，查 cnt[6 - 3] = cnt[3] = 1，answer = 2——这次配上的是前缀 [1, 2]，对应的子数组是 [3]；写入后 cnt = {0: 1, 1: 1, 3: 1, 6: 1}。返回 2。若把 cnt[0] = 1 这个初始项去掉，第二步的查询会得到 $0$，[1, 2] 这个答案就凭空消失了。

代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        // 空前缀：让「从下标 0 开始」的子数组也能被配对。
        cnt.put(0, 1);
        int answer = 0, s = 0;
        for (int x : nums) {
            s += x;
            // 必须先查后写，否则 k == 0 时当前前缀和会和自己配对。
            answer += cnt.getOrDefault(s - k, 0);
            cnt.merge(s, 1, Integer::sum);
        }
        return answer;
    }
}

func subarraySum(nums []int, k int) (answer int) {
    cnt := map[int]int{0: 1}
    s := 0
    for _, x := range nums {
        s += x
        answer += cnt[s-k]
        cnt[s]++
    }
    return
}

复杂度分析

时间复杂度：$O(n)$。数组只扫一遍，每个元素做一次加法、一次哈希查询和一次哈希写入，均摊都是常数。凭的是前缀和把「枚举左端点」换成了「查一次哈希表」。

空间复杂度：$O(n)$。哈希表最多存下 $n + 1$ 个互不相同的前缀和值（含空前缀）。这是用空间换时间的代价，也是本题无法做到 $O(1)$ 空间的原因——元素可负让窗口失效，就必须记住全部历史前缀和。

关键点总结

「连续子数组 + 和为定值 + 元素可负」是前缀和 + 哈希表的标准触发组合；只要看到「可能有负数」，就该立刻放弃滑动窗口。

核心恒等式是 $\text{区间和} = s_j - s_{i-1}$，它把「枚举区间」降维成「查配对」。这条恒等式换成异或前缀、模数前缀、$\pm 1$ 前缀后，能覆盖一大批变体题。

先查询后写入是这类题的铁律，它对应「左端点必须严格早于右端点」这条语义。写反了在 k != 0 时往往看不出问题，恰恰是最阴险的 bug。

cnt[0] = 1 的初始化代表空前缀，是「以数组开头为左端」的答案的唯一来源；它和「先查后写」共同构成本题的两个必答点。

哈希表存什么由问的是什么决定：求个数存出现次数，求最长/最短存最早出现的下标，求是否存在存布尔值。定义一旦选定就不能中途换语义。

面试视角：这道题几乎必被追问「为什么不能用滑动窗口」，标准回答是「元素可为负，区间和随窗口扩张不再单调，收缩的判据不成立」；第二个高频追问是「先写入再查询会怎样」，回答是「k = 0 时每个位置都会和自己配出一个长度为零的假解」。能把这两问答利落，比写出代码本身更重要。

易错点总结

错误写法：忘记 cnt.put(0, 1)。输入 nums = [1, 2, 3], k = 3 会漏掉 [1, 2]，返回 1 而不是 2；输入 nums = [3], k = 3 会返回 0。

错误写法：先 cnt.merge(s, 1, ...) 再查询。输入 nums = [1, 2, 3], k = 0 时每个位置都会查到自己刚写入的那一份，返回 3 而不是 0。

错误写法：查询写成 cnt.get(k - s)。方向反了，输入 nums = [1, 2, 3], k = 3 会返回 1 而不是 2。

错误写法：answer += 1 而不是 answer += cnt.get(s - k)。同一个前缀和出现多次时只算了一次，输入 nums = [1, -1, 1, -1], k = 0 会返回 3 而不是 4。

错误写法：哈希表存 Set<Integer> 只记「是否出现过」。同样在 nums = [1, -1, 1, -1], k = 0 上少算，返回 3 而不是 4。

错误写法：改用滑动窗口，和超过 k 就收缩左端。输入 nums = [1, -1, 0], k = 0 时窗口在 s == 0 处收缩，会漏掉 [1, -1, 0] 与 [0] 之外的解，返回值小于正确的 3。

错误写法：预先构造完整前缀和数组后再双层枚举配对。逻辑对但复杂度是 $O(n^2)$，$2 \times 10^4$ 的数据会超时；而且额外多开了一个数组。

错误写法：把 s 声明成会溢出的类型。元素范围 $[-1000, 1000]$、长度 $2 \times 10^4$ 时前缀和绝对值上界是 $2 \times 10^7$，int 足够；但若把这套代码搬到元素范围更大的变体题（如 974、1074）而不换成 long，前缀和会溢出并让哈希键彻底错乱。

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	与本题同题，可直接套用同一份「先查后写」
LCR 011. 连续数组	中等	把 $0$ 映射成 $-1$ 后求和为 $0$ 的最长子数组，哈希表改存最早下标
525. 连续数组	中等	与 LCR 011 同题，是「存次数还是存下标」这一取舍的经典对照
325. 和等于 k 的最长子数组长度	中等	求最长长度，哈希表只保留每个前缀和第一次出现的位置
974. 和可被 K 整除的子数组	中等	键换成前缀和对 `k` 的余数，负数取模要先加 `k` 再取模
面试题 17.05. 字母与数字	中等	字母记 $+1$、数字记 $-1$，求最长平衡段并要求返回具体区间
1074. 元素和为目标值的子矩阵数量	困难	二维版本，需枚举上下边界把每一对压成一维再套本题