企业官网建设流程全解析

LeetCode-Go 题解：560. Subarray Sum Equals K（前缀和 + 哈希表 O(n) 解法全解析）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文基于 LeetCode-Go 开源仓库中 0560.Subarray-Sum-Equals-K 的题解文档，系统讲解 LeetCode 560 题「和为 K 的子数组」的完整解题路径：为什么滑动窗口在此题失效、如何把「区间和」转化为「两数之和」式的前缀和查找问题，以及如何用哈希表把暴力O(n^2)优化到O(n)。读完本文，你将掌握「前缀和 + 哈希表」这一类连续子数组计数问题的通用模板，并能直接运行仓库内已通过测试的 Go 实现进行验证。

题目理解：统计和为 K 的连续子数组

题目要求（原文见 README.md）：

Given an array of integersnumsand an integerk, return the total number of continuous subarrays whose sum equals tok.

即：给定一个整数数组nums和一个整数k，统计并返回该数组中和为k的连续子数组的个数。注意是「连续子数组」（continuous subarrays），不是任意子序列，也不是去重后的不同子数组集合，而是所有起点、终点组合都要逐一计数。

示例与约束

示例 1：

Input: nums = [1,1,1], k = 2 Output: 2

解释：和为 2 的连续子数组有两个：[1,1]（下标 0~1）和[1,1]（下标 1~2）。

示例 2：

Input: nums = [1,2,3], k = 3 Output: 2

解释：和为 3 的连续子数组有两个：[1,2]（下标 0~1）和[3]（下标 2）。

约束条件：

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

约束中的两个细节决定了算法选型：一是数组最长可达 2 万，暴力枚举所有起点终点是O(n^2)，在极端数据下会超时；二是nums[i]允许为负数，这直接否决了滑动窗口方案（详见下一节）。

为什么不能用滑动窗口：负数是关键

原文档在 解题思路 中开门见山地给出结论：

此题不能使用滑动窗口来解。因为nums[i]可能为负数。

滑动窗口（双指针）之所以常用于「子数组和」类问题（如 209. Minimum Size Subarray Sum），依赖一个核心性质：窗口右移时窗口和单调变化。当所有元素非负时，右指针扩张会让和只增不减，左指针收缩会让和只减不增，因此可以安全地根据当前和与目标的大小关系移动指针。

而本题nums[i]的取值范围是[-1000, 1000]，包含负数。此时：

• 右指针扩张，窗口和可能变小；
• 左指针收缩，窗口和可能变大。

窗口和不再单调，双指针的移动依据被破坏，滑动窗口无法正确枚举所有可能区间，因此必须另寻他路——前缀和。

核心解法：前缀和 + 哈希表

第一步：暴力前缀和，把区间和转化为前缀和之差

定义前缀和prefixSum[i]为数组前i个元素之和（prefixSum[0] = 0）。则任意连续区间[i, j]（下标从 1 计）的和可以表示为：

sum(nums[i..j]) = prefixSum[j] - prefixSum[i-1]

于是「是否存在和为 k 的区间[i, j]」等价于：

prefixSum[j] - prefixSum[i-1] == k ⇔ prefixSum[j] == k + prefixSum[i-1]

直接枚举所有i, j对并比较差值，时间复杂度为O(n^2)。原文档明确指出：

前缀和的思路可以解答此题，但是时间复杂度有点高了，O(n^2)。考虑优化时间复杂度。

第二步：A + B = K 的转换，复用 Two Sum 的优化思想

原文档给出了关键的等价变形：

题目要求找到连续区间和为k的子区间总数，即区间[i,j]内的和为 K ⇒prefixSum[j] - prefixSum[i-1] == k。所以prefixSum[j] == k - prefixSum[i-1]。这样转换以后，题目就转换成类似 A + B = K 的问题了。

注意这里的符号差异：如果固定j，遍历历史前缀和prefixSum[i-1]，那么我们要找的是满足prefixSum[i-1] == prefixSum[j] - k的历史前缀和。也就是说，每到一个位置j，只要知道此前有多少个前缀和等于prefixSum[j] - k，这些位置就都能与j组成一个和为 k 的区间。

这与 LeetCode 第 1 题 Two Sum「A + B = K，用哈希表存遍历过的值，O(1) 查互补值」的思路完全一致——原文档称之为「LeetCode 第一题的优化思路拿来用」，仓库中 1. Two Sum.go 的实现正是这个模板的原始出处：

func twoSum(nums []int, target int) []int { m := make(map[int]int) for k, v := range nums { if idx, ok := m[target-v]; ok { return []int{idx, k} } m[v] = k } return nil }

Two Sum 是「哈希表存下标、查互补值」，本题则升级为「哈希表存前缀和出现次数、查互补前缀和的计数」，一脉相承。

第三步：一次遍历 + 计数累积

算法流程：

1. 维护当前累计前缀和pre，初始为 0；
2. 维护哈希表m，键为「出现过的前缀和」，值为「该前缀和出现的次数」；初始化m[0] = 1，表示空前缀（prefixSum[0] = 0出现 1 次），这是为了正确统计从下标 0 开始的区间；
3. 遍历数组，每步先累加pre += nums[i]；
4. 查询m[pre-k]：若存在，说明此前有m[pre-k]个前缀和位置能与当前位置构成和为 k 的区间，累加入答案；
5. 将当前前缀和pre的计数加 1，供后续位置使用；
6. 返回总计数。

m[0] = 1这一步是关键细节：例如示例 1 中nums = [1,1,1], k = 2，遍历到i = 1时pre = 2，m[pre-k] = m[0] = 1，恰好统计出从下标 0 开始的区间[0,1]，可见空前缀的初始化不可或缺。

完整 Go 实现与逐行注释

以下是仓库 560. Subarray Sum Equals K.go 中的完整实现（与文档 README.md 中的代码一致），在此补充逐行注释便于理解：

package leetcode func subarraySum(nums []int, k int) int { count, pre := 0, 0 // count：满足条件的子数组个数；pre：当前累积前缀和 m := map[int]int{} // m：记录每个前缀和出现过的次数 m[0] = 1 // 空前缀（前缀和为 0）视为出现 1 次，用于统计从下标 0 开始的区间 for i := 0; i < len(nums); i++ { pre += nums[i] // 累加得到当前位置的前缀和 if _, ok := m[pre-k]; ok { // 此前存在前缀和 == pre-k 的位置 count += m[pre-k] // 每个这样的位置都能与当前位置构成一个和为 k 的区间 } m[pre] += 1 // 记录当前前缀和，供后续位置查询 } return count }

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。每个元素只被遍历一次，哈希表的插入与查询平均为O(1)，整体由O(n^2)暴力降至线性。
• 空间复杂度：O(n)，最坏情况下前缀和互不相同，哈希表需要存储 n 个键。

一个关键注意点：先查询、后写入

遍历中必须先执行count += m[pre-k]再执行m[pre] += 1，顺序不能颠倒。原因有二：

1. 区间要求「连续」且长度至少为 1，当前元素自身不能与「当前时刻的自己」配对成区间，因此当前前缀和不能先于查询写入；
2. 数组允许负数，同一个前缀和可能在多个位置重复出现，计数必须累积（m[pre] += 1而非置 1），这正体现了与 Two Sum「存下标、命中即返回」的本质差异——本题需要统计所有配对。

边界情况与易错点

结合测试用例可以梳理出本题最容易踩坑的边界场景：

1. 单元素数组且 k 不为该元素：

Input: nums = [1], k = 0 Output: 0

遍历时pre = 1，查询m[1-0] = m[1] = 0，计数保持 0，结果正确。

2. 负数参与构成和为 0 的区间：

Input: nums = [-1, -1, 1], k = 0 Output: 1

只有区间[-1, 1]（下标 1~2）和为 0。滑动窗口在此类用例上无法正确工作。

3. 连续多个区间都满足条件（前缀和重复）：

Input: nums = [1, -1, 0], k = 0 Output: 3

满足条件的区间为[1,-1]（下标 0~1）、[-1,0]（下标 1~2）和[1,-1,0]（下标 0~2）共 3 个。注意整个数组和为 0 的区间也被正确计入，这正是m[0] = 1初始化与「计数累积」共同作用的结果。

上述用例全部收录于仓库测试文件 560. Subarray Sum Equals K_test.go 中。

源码与测试验证：如何在本仓库运行

本仓库对每个题目都遵循「题解文档 + 实现源码 + 测试用例」三件套的组织方式。本题三个文件位于同一目录下：

• README.md：题目原文、中文大意与解题思路；
• 560. Subarray Sum Equals K.go：subarraySum函数实现；
• 560. Subarray Sum Equals K_test.go：基于表驱动（table-driven）风格的测试，覆盖示例与边界用例。

测试文件的结构清晰可复用：question560组合结构体把输入（para560：nums与k）和期望输出（ans560）绑定在一起，Test_Problem560遍历qs切片逐一断言。你可以直接在该目录运行：

go test -v -run Test_Problem560 ./leetcode/0560.Subarray-Sum-Equals-K/

若要验证整体覆盖率，仓库根目录的 gotest.sh 提供了一条针对全部题解的测试命令：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

运行后可用go tool cover -func=coverage.txt查看各题解函数的覆盖情况。需要说明的是，该脚本是针对整个leetcode/包目录的批量验证；单题快速调试仍推荐上面的-run Test_Problem560方式。

扩展：一类题的通用模板

「前缀和 + 哈希表计数」不止解决 560 题，它是处理连续子数组（子串）计数/存在性类问题的通用范式。当题目从「计数等于 k」变化为「计数大于等于 k」「计数可被整除」「计数不超过 k」时，只需调整哈希表查询逻辑或搭配前缀和的有序结构（如平衡树/树状数组）即可迁移。常见变体包括：

• 和为 k 的最长子数组（同前缀和模板，记录首次出现下标）；
• 和可被 k 整除的子数组（键取模后计数）；
• 和为 k 的子数组个数不超过某上限（配合有序容器求排名）。

理解 560 题的「先查后写、计数累积、空前缀初始化」三个要点后，这些变体都能在几分钟内写出正确的线性解法。若希望系统复习前缀和类题目，可继续浏览仓库leetcode/目录下其他题解文档，结合 README.md 中的总体索引定位同类题目。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go