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.mdGiven an array of integersnumsand an integerk, return the total number of continuous subarrays whose sum equals tok.即给定一个整数数组nums和一个整数k统计并返回该数组中和为k的连续子数组的个数。注意是「连续子数组」continuous subarrays不是任意子序列也不是去重后的不同子数组集合而是所有起点、终点组合都要逐一计数。示例与约束示例 1Input: nums [1,1,1], k 2 Output: 2解释和为 2 的连续子数组有两个[1,1]下标 0~1和[1,1]下标 1~2。示例 2Input: 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 是「哈希表存下标、查互补值」本题则升级为「哈希表存前缀和出现次数、查互补前缀和的计数」一脉相承。第三步一次遍历 计数累积算法流程维护当前累计前缀和pre初始为 0维护哈希表m键为「出现过的前缀和」值为「该前缀和出现的次数」初始化m[0] 1表示空前缀prefixSum[0] 0出现 1 次这是为了正确统计从下标 0 开始的区间遍历数组每步先累加pre nums[i]查询m[pre-k]若存在说明此前有m[pre-k]个前缀和位置能与当前位置构成和为 k 的区间累加入答案将当前前缀和pre的计数加 1供后续位置使用返回总计数。m[0] 1这一步是关键细节例如示例 1 中nums [1,1,1], k 2遍历到i 1时pre 2m[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当前元素自身不能与「当前时刻的自己」配对成区间因此当前前缀和不能先于查询写入数组允许负数同一个前缀和可能在多个位置重复出现计数必须累积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题目原文、中文大意与解题思路Subarray Sum Equals K.gosubarraySum函数实现Subarray Sum Equals K_test.go基于表驱动table-driven风格的测试覆盖示例与边界用例。测试文件的结构清晰可复用question560组合结构体把输入para560nums与k和期望输出ans560绑定在一起Test_Problem560遍历qs切片逐一断言。你可以直接在该目录运行go test -v -run Test_Problem560 ./leetcode/0560.Subarray-Sum-Equals-K/若要验证整体覆盖率仓库根目录的 gotest.sh 提供了一条针对全部题解的测试命令go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...运行后可用go tool cover -funccoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考