LeetCode 560. 和为 K 的子数组

约 5 分钟
文章信息 24 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 小米 百度 网易 快手 滴滴 B站 虾皮 猿辅导
标签
数组 哈希表 前缀和

题目描述

✅ 560. 和为 K 的子数组

image-20260928194418800

题意分析

给定整数数组 nums 和整数 k，统计元素和恰好等于 k 的非空连续子数组数量。子数组由一段连续下标确定，不允许跳过中间元素，也不要求不同答案互不重叠。

不同的起止位置算不同子数组，即使其中的数值完全一样也要分别计数。元素和 k 都可能为负或为零；题目求的是满足条件的区间数量，不是是否存在，也不是最长区间的长度。

解法：前缀和 + 哈希表计数

核心思路

[!blue]

数组含有负数，右边加入一个数时，区间和可能增加也可能减少；左边移出一个数时也一样。因此无法仅凭当前和大于或小于 k，决定普通滑动窗口应该向哪边收缩。改用前缀和，可以直接把区间和写成两个位置之间的差。

令 P[r] 表示前 r 个元素的和，P[0] = 0。从下标 l 到 r - 1 的子数组之和为 P[r] - P[l]，其中 l < r。要求它等于 k，就等价于在当前位置之前寻找 P[l] = P[r] - k 的前缀。

从左向右枚举右端点，用 prefixSum 表示当前的 P[r]，哈希表 freq 保存所有更早前缀和的出现次数。查询 freq[prefixSum - k]，就得到了以当前元素为结尾的合法子数组数量。相同前缀和可能出现在多个位置，每个位置对应不同左边界，所以要累加它们的次数，不能只判断是否出现。

初始设置 freq[0] = 1，表示数组开始之前的空前缀。它只充当左边界，使从下标 0 开始的子数组也能用相同公式统计，并不是提前计入一个空子数组。

每轮必须先查询，再记录当前前缀和。这样查询时表中只含 P[0] 到 P[r - 1]，保证左边界严格早于右边界；若先记录当前 P[r]，当 k = 0 时就会把同一位置相减的空区间也算进去。每个合法区间只在处理自己的右端点时被统计一次，因此既不漏计也不重复。

解题步骤

  1. 初始化 freq[0] = 1，令 prefixSum = 0、ans = 0。
  2. 遍历每个元素，将它累加到 prefixSum，得到当前右端点对应的前缀和。
  3. 将历史前缀 prefixSum - k 的出现次数加到 ans；不存在时按零次处理。
  4. 将当前 prefixSum 的次数加一，供后面的右端点查询。
  5. 遍历结束，返回累计的子数组数量。

代码实现

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

        freq.put(0, 1);
        int prefixSum = 0;
        int ans = 0;

        for (int num : nums) {
            prefixSum += num;
            // 之前的 prefixSum-k 都可以作为当前子数组的左边界前缀。
            ans += freq.getOrDefault(prefixSum - k, 0);
            freq.put(prefixSum, freq.getOrDefault(prefixSum, 0) + 1);
        }

        return ans;
    }
}

func subarraySum(nums []int, k int) int {
    freq := map[int]int{0: 1}
    prefixSum := 0
    ans := 0

    for _, num := range nums {
        prefixSum += num
        // 查找能与当前前缀和相差 k 的历史前缀。
        ans += freq[prefixSum-k]
        freq[prefixSum]++
    }

    return ans
}

复杂度分析

  • 时间复杂度：平均 $O(n)$，每个元素只进行一次哈希查询和一次更新，单次平均为 $O(1)$。
  • 空间复杂度：$O(n)$，最多保存初始空前缀和 n 个非空前缀的计数，不需要额外建立完整前缀和数组。

关键点总结

[!green]

  • P[r] - P[l] = k 把连续区间求和转成历史前缀值的计数。
  • 哈希表中的次数代表可选左边界数量，重复前缀必须保留全部次数。
  • 空前缀负责覆盖从头开始的区间，先查询后写入负责排除空区间。

易错点总结

[!yellow]

  • 用区间和与 k 的大小决定滑动窗口方向，会因负数破坏单调性而漏解。
  • 忘记初始的零前缀，会漏掉所有从数组开头开始、和为 k 的区间。
  • 先增加当前前缀次数再查询，会在 k = 0 时把空区间错误计入。
  • 命中历史前缀时只执行 ans++，会漏掉同一前缀和对应的其他左边界。
  • 使用集合、只保存一个下标，或把次数直接覆盖为一，都无法完成本题要求的全部区间计数。

相似题目

题目 难度 关联与区别
523. 连续的子数组和 中等 同样比较两个前缀，原题把相等差值条件改为前缀余数相等，并限制最小长度。
437. 路径总和 III 中等 把数组前缀和计数推广到树上向下路径，需要退出分支时撤销前缀频次。
325. 和等于 k 的最长子数组长度 中等 前缀和配合哈希表查找所需历史前缀；本题存前缀出现次数以统计精确和，该题存最早前缀下标以最大化长度。
930. 和相同的二元子数组 中等 前缀和配合哈希表查找所需历史前缀；本题存前缀出现次数以统计精确和，该题二进制数组上统计目标和。
1248. 统计「优美子数组」 中等 前缀和配合哈希表查找所需历史前缀；本题存前缀出现次数以统计精确和，该题把奇数映射为 1 后统计精确数量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/13096231
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！