和为 K 的子数组:前缀和与哈希表组合技 —— LogicStack-LeetCode 刷穿 LeetCode 560 题深度解析

原创2026-10-09 20:22:241,902 阅读
文章标签:教程文档

和为 K 的子数组:前缀和与哈希表组合技 —— LogicStack-LeetCode 刷穿 LeetCode 560 题深度解析

本文是 LogicStack-LeetCode(公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列)中 LeetCode 560 号题「和为 K 的子数组」的完整技术解析。文章以仓库内 560. 和为 K 的子数组(中等).md 为主体,结合仓库中「前缀和」「哈希表」两大算法索引,讲解如何在 O(n) 时间内统计数组中和为 k 的连续子数组个数,并延伸探讨该思路在二维矩阵、树上路径等场景中的统一应用。读完你将掌握「前缀和 + 哈希表」这一高频组合技巧的本质推导、多语言实现细节及其变体题的通解思路。

题目描述

这是 LeetCode 上的 560 号题「和为 K 的子数组」,难度为中等,核心 Tag 为**「前缀和」与「哈希表」**。

给你一个整数数组 nums 和一个整数 k,请你统计并返回该数组中和为 k 的子数组的个数。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

数据范围(即本题的约束前提,也是选择算法的依据):

  • 1 <= nums.length <= 2 × 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

注意两点关键信息:其一,nums[i] 可为负数,因此不能用「双指针/滑动窗口」这类依赖单调性的做法;其二,n 最大为 2 × 10^4,朴素的 O(n^2) 枚举所有子数组并求和(O(n^3) 更不必说)在数据量较大时会超时,必须将复杂度优化到 O(n)。

为什么朴素枚举不可行

最直观的思路是枚举每个子数组的起点与终点,再累加求和判断是否等于 k。但子数组个数为 O(n^2),如果每次求和都重新累加,总复杂度为 O(n^3);即便用「增量求和」技巧,也只能降到 O(n^2),在 n = 2 × 10^4 时计算量达到约 4 × 10^8,处于超时边缘。

由于数组元素存在负数,子数组和并不随长度单调变化,「滑动窗口」这一经典优化手段在此题中失效。 因此需要引入前缀和,把「区间和」的求解从每次 O(区间长度) 降为 O(1),再配合哈希表把「查找」也降到 O(1),从而整体达到线性复杂度。

核心思路:前缀和 + 哈希表

1. 前缀和的定义

预处理一个前缀和数组 sum(下标默认从 1 开始),其中:

sum[i] = nums[0] + nums[1] + ... + nums[i-1]

即 sum[i] 表示原数组前 i 个元素的和。这样任意区间 [l, r](原数组下标从 0 计)的和都可以表示为:

sum[r + 1] - sum[l]

一次 O(n) 的预处理,即可在 O(1) 时间内回答任意区间和。

2. 统计「以每个位置为结尾」的合法子数组

原文档给出的关键洞察是:统计以每一个 nums[i] 为结尾、和为 k 的子数组数量,加总即是答案。

对于以原数组第 i 个元素(即前缀和下标 i)为结尾的子数组,其可能的左端点范围为 [0, i](对应前缀和下标 [0, i])。若子数组 [l, i] 的和为 k,则等价于:

sum[i + 1] - sum[l] = k   ⟹   sum[l] = sum[i + 1] - k

因此问题转化为:在遍历到前缀和下标 i 时,sum[0..i] 中有多少个位置的值等于 sum[i + 1] - k。

3. 用哈希表同步记录前缀和出现次数

为了在 O(1) 时间内回答「有多少个历史前缀和等于 target = sum[i + 1] - k」,可以在遍历过程中用哈希表 map 同步维护「每个前缀和值出现的次数」。

细节一:初始化 map[0] = 1。 前缀和 sum[0] = 0 代表「空前缀」,它对应左端点 l = 0(即子数组从原数组开头取起)。若某次 sum[i + 1] - k = 0,说明 [0, i] 这个整段前缀本身就是合法子数组,必须在初始化时就把 0 计入哈希表才能正确统计。

细节二:先查询、后更新。 对于每个 i,应当先查询 map[sum[i + 1] - k] 累加进答案,再把当前的 sum[i + 1] 计数加一。如果先更新再查询,就会把「以当前元素为结尾、长度为 0」的空子数组也统计进去,造成错误计数。

细节三:getOrDefault 与 find 的写法。 查询一个不存在的键时,Java 用 map.getOrDefault(d, 0) 返回默认值 0;C++ 需先用 map.find(d) != map.end() 判断存在再累加;Python 的 defaultdict(int) 访问不存在的键会自动返回 0。

多语言实现(完整可运行代码)

以下四段代码均来自原文档,可直接在 LeetCode 或本地调试环境运行:

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[] sum = new int[n + 10];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 1; i <= n; i++) {
            int t = sum[i], d = t - k;
            ans += map.getOrDefault(d, 0);
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        vector<int> sumv(n + 1, 0);
        for (int i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + nums[i - 1];
        unordered_map<int, int> map;
        map[0] = 1;
        for (int i = 1; i <= n; i++) {
            int t = sumv[i], d = t - k;
            if (map.find(d) != map.end()) ans += map[d];
            map[t]++;
        }
        return ans;
    }
};

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n, ans = len(nums), 0
        sumv = [0] * (n + 10)
        for i in range(1, n + 1):
            sumv[i] = sumv[i - 1] + nums[i - 1]
        mapping = defaultdict(int)
        mapping[0] = 1
        for i in range(1, n + 1):
            t = sumv[i]
            d = t - k
            ans += mapping[d]
            mapping[t] += 1
        return ans

TypeScript

function subarraySum(nums: number[], k: number): number {
    let n = nums.length, ans = 0
    const sum = new Array<number>(n + 10).fill(0)
    for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1]
    const map = new Map<number, number>()
    map.set(0, 1)
    for (let i = 1; i <= n; i++) {
        const t = sum[i], d = t - k
        if (map.has(d)) ans += map.get(d)
        map.set(t, map.has(t) ? map.get(t) + 1 : 1)
    }
    return ans
};

注:上述代码为原文档实现,前缀和数组多申请了 n + 10 的长度,属于「哨兵余量」的稳健写法;若追求最小内存,改为 n + 1 完全等价。

复杂度分析

  • 时间复杂度:预处理前缀和数组为 O(n),单次遍历配合哈希表统计答案为 O(n),整体复杂度 O(n)(哈希表读写均摊 O(1))。
  • 空间复杂度:前缀和数组与哈希表各占用 O(n) 空间,整体 O(n)。

相比朴素枚举的 O(n^2) 甚至 O(n^3),这一解法在数据范围上限(n = 2 × 10^4)下表现稳健,这正是它成为「前缀和经典应用题」的原因。

为什么 map[0] = 1 必不可少:一个推演示例

以示例 nums = [1,1,1], k = 2 手动推演一遍流程,可以直观理解「先查询、后更新」与 map[0] = 1 的作用:

前缀和下标 i sum[i] 查询目标 sum[i] - k 命中次数 累计 ans 更新 map
0 0 - - 0 {0:1}
1 1 -1 0 0 {0:1, 1:1}
2 2 0 1(空前缀) 1 {0:1, 1:1, 2:1}
3 3 1 1(前缀下标1) 2 {0:1, 1:1, 2:1, 3:1}

最终 ans = 2,对应子数组 [1,1](下标 0-1)与 [1,1](下标 1-2),与预期一致。注意第二次命中依赖的是哈希表中早已存在的前缀和 sum[1] = 1,这正体现了「先查询再更新」的顺序正确性。

仓库中的同类题与通解体系

本题是「前缀和 + 哈希表」组合的基石题,LogicStack-LeetCode 仓库在 Index/前缀和.md 与 Index/哈希表.md 两个算法索引中均有收录(推荐指数 🤩🤩🤩🤩🤩),并在多个系列题解中反复使用同一套路:

  • 剑指 Offer II 010. 和为 k 的子数组(中等):与本题完全相同的题目与解法(仓库内代码为 Java 与 TypeScript 双版本),适合作为同一思路的对照复习。
  • 523. 连续的子数组和(中等):把「等于 k」改为「是 k 的倍数」。关键推导为 sum[j] - sum[i-1] = n×k 等价于 sum[j] ≡ sum[i-1] (mod k),于是只需用 HashSet 记录「前缀和对 k 的取余结果」,并注意子数组长度至少为 2(循环从 i = 2 开始、延迟一个位置插入哈希表)。这是「前缀和 + 哈希」思路在模运算维度上的自然延伸。
  • 437. 路径总和 III(中等):把一维数组换成「二叉树中的向下路径」。由于根到任意节点的路径唯一,统计「以每个节点为结尾、和为 targetSum 的路径数」本质上就是一个一维前缀和问题;唯一需要注意的是回溯时把当前前缀和从哈希表中删除,防止统计到跨越左右两个方向的非法路径。
  • 1074. 元素和为目标值的子矩阵数量(困难):将本题推广到二维。先做二维前缀和,然后枚举子矩阵的上下边界,在右边界右移的过程中把「右边界到原矩阵左边界」的矩阵和存入哈希表,再用 cur - target 查找合法的左边界,从而把 O(n^4) 的朴素枚举优化到 O(m × n^2)。

可以清晰看到一条方法论主线:凡是「统计连续区间/路径/子矩阵的和等于某值」的问题,都可以尝试「前缀和预处理 + 哈希表查历史」来把枚举配对降为线性或准线性复杂度。本题正是这一通解的最小、最干净的载体。

小结

560 号题是「前缀和 + 哈希表」组合技巧的入门必刷题:

  • 因为元素可正可负,滑动窗口失效,必须使用前缀和把区间和降为 O(1) 查询;
  • 统计「以每个位置结尾的合法子数组数」并累加,是避免重复枚举左右端点的关键视角;
  • 哈希表同步记录历史前缀和出现次数,配合 map[0] = 1 与「先查询、后更新」两个细节,即可在 O(n) 时间内完成统计;
  • 该套路可自然推广到「模 k 同余」(523)、「树上前缀和」(437)、「二维子矩阵」(1074)等系列变体,值得作为模板反复演练。

需要更多同类练习时,可回到仓库的 Index/前缀和.md 与 Index/哈希表.md 按推荐指数挑选题目,形成「一题入门、多题巩固、变体检验」的完整刷题闭环。

登录后查看全文
LogicStack-LeetCode