LeetCode LCR 010. 和为 K 的子数组

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 哈希表 LCR 前缀和

题目描述

✅ LCR 010. 和为 K 的子数组

image-20260928234753423

题意分析

给定整数数组与目标 k，统计和恰好等于 k 的非空连续子数组个数。相同数值序列出现在不同位置时，也对应不同子数组。

元素可以为负或为零，目标也不限定为正。扩张区间可能增加、减少或保持区间和，因此不能直接套用“和大了就缩窗”的正数滑动窗口规则。

解法：前缀和频次配对

核心思路

[!blue]

定义前缀和为从数组开头到某个位置的累计值，另有一个位于第一个元素之前、值为零的空前缀。任意连续区间的和，都等于结束位置的前缀和减去开始位置之前的前缀和。

扫描到当前右端，累计值为 s 时，要让区间和等于 k，就需要一个更早的前缀和值为 s - k。因此不必逐个枚举左端，只要知道这个历史前缀值出现过几次，就能一次加入相同数量的合法区间。

哈希表 cnt 保存每个历史前缀和的出现次数。同一个值可能来自不同位置，每个位置都给出一个不同的左端，所以必须累加频次，不能只保存是否出现或某一个下标。

初始的 cnt[0] = 1 代表空前缀，使从数组开头开始的答案也能配对。之后如果再次出现零和前缀，仍正常增加它的频次；空前缀只是其中一个来源，并不是值为零的前缀只能出现于开头。

每轮先将当前元素加入 s，再查询 cnt[s - k]，最后登记当前 s。查询时表里只包含更早前缀，保证区间非空；若先登记，k == 0 时当前前缀会与自身配对，错误计入空区间。每个区间只在它的右端被统计一次。

解题步骤

  1. 初始化前缀和与答案为零，预置空前缀的频次 cnt[0] = 1。
  2. 遍历元素并更新当前前缀和 s。
  3. 将历史表中 s - k 的次数加入答案，未出现时贡献零。
  4. 再把当前 s 的出现次数加一，留给后续右端使用。
  5. 返回累计的子数组数量。

代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();

        // 空前缀：让「从下标 0 开始」的子数组也能被配对。
        cnt.put(0, 1);
        int answer = 0;
        int 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
}

复杂度分析

设数组长度为 $n$。

  • 时间复杂度：期望 $O(n)$，每个元素只触发常数次哈希操作。
  • 辅助空间复杂度：$O(n)$，最多记录 $n+1$ 种前缀和值，包含空前缀。

关键点总结

[!green]

  • 区间和转换为前缀差，固定右端后查询历史互补值。
  • 求数量就存频次，重复前缀对应不同的合法左端。
  • 空前缀覆盖从头开始的区间，先查询后登记排除空区间。

易错点总结

[!yellow]

  • cnt[0] 必须初始化为一，空前缀确实存在一次。
  • 前缀和可能反复相同，覆盖为一次或只使用集合都会少计答案。
  • 先登记当前前缀会在 k == 0 时产生自身配对。
  • 查询对象是 s - k，不是 k - s，它表示区间左端之前的前缀和。
  • 不要混用求最长区间时保存最早位置的策略，本题需要所有出现位置的计数。

相似题目

题目 难度 关联与区别
523. 连续的子数组和 中等 同样比较两个前缀，原题把相等差值条件改为前缀余数相等，并限制最小长度。
437. 路径总和 III 中等 把数组前缀和计数推广到树上向下路径，需要退出分支时撤销前缀频次。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/43675801
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！