教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote「算法通关手册」LeetCode 题解系列中的一篇围绕题号0325. Maximum Size Subarray Sum Equals k和等于 k 的最长子数组长度展开。这是一道经典的「前缀和 哈希表」应用题在数组中包含负数的前提下滑动窗口失效只有借助前缀和的数学性质才能把「找和为 k 的最长子数组」转化为「查前缀和差值」从而在单次遍历内以 O(n) 时间求解。读完本文你将掌握前缀和的推导过程、哈希表记录「首次出现位置」的关键技巧以及它在全仓库 1000 道题目体系docs/solutions中的姊妹题串联方式。题目大意与数据范围描述给定一个整数数组nums和一个目标值k。要求找到和等于k的最长连续子数组长度。如果不存在任意一个符合要求的子数组则返回0。说明数据范围是本题选型的关键依据$1 \le nums.length \le 2 \times 10^{5}$$-10^{4} \le nums[i] \le 10^{4}$$-10^{9} \le k \le 10^{9}$示例示例 1输入: nums [1,-1,5,-2,3], k 3 输出: 4 解释: 子数组 [1, -1, 5, -2] 和等于 3且长度最长。示例 2输入: nums [-2,-1,2,1], k 1 输出: 2 解释: 子数组 [-1, 2] 和等于 1且长度最长。题目原链接与完整题解收录于 maximum-size-subarray-sum-equals-k.md该题也位列 0300-0399 章节索引 与仓库的题目分类清单 00_06_categories_list.md 中。为什么不能直接用滑动窗口很多「连续子数组求和」问题可以用滑动窗口解决例如仓库中同为「子数组求和」主题的 0209. 长度最小的子数组。但滑动窗口成立的前提是窗口移动方向确定——它要求元素全部非负右移右指针时窗口和单调不减。本题的nums[i]取值范围为 $-10^4 \le nums[i] \le 10^4$数组中允许出现负数。负数的存在让窗口和不再单调右指针右移时窗口和可能变小左指针收缩时窗口和可能变大因此无法通过双指针单调收缩来维护「和为 k」的窗口。此时必须换思路——用前缀和把「子数组和」转化为「两个前缀和的差」。思路 1前缀和 哈希表核心推导把子数组和变成前缀和之差计算前缀和定义 $prefix_sum[i]$ 表示数组前 $i$ 个元素的和即 $$prefix_sum[i] \sum_{j0}^{i-1} nums[j]$$ 它可以通过递推得到$prefix_sum[i] prefix_sum[i-1] nums[i-1]$。利用前缀和性质对于子数组 $nums[i:j1]$即下标区间 $[i, j]$其和为 $$prefix_sum[j1] - prefix_sum[i]$$ 如果这个和等于 $k$则有 $$prefix_sum[j1] - prefix_sum[i] k$$ 移项得 $$prefix_sum[i] prefix_sum[j1] - k$$也就是说当我们站在位置 $j1$只要历史上出现过前缀和等于 $prefix_sum[j1] - k$那么从该历史位置到当前位置之间的子数组和就恰好等于 $k$。哈希表记录首次出现位置使用哈希表prefix_map记录每个前缀和第一次出现的位置。遍历到当前位置时若prefix_sum - k已存在于表中说明存在一个和为 $k$ 的子数组。更新最长长度每次找到满足条件的子数组时用max_length max(max_length, current_length)更新答案。关键点决定答案正确性的三处细节初始化prefix_map {0: -1}。$prefix_sum[0] 0$ 对应空数组位置记为 $-1$。这样当整个前缀nums[0:i]的和恰好等于 $k$ 时prefix_sum - k 0能在表中命中子数组长度为i - (-1) i 1空数组位置-1正是为了统一处理「从头开始」的子数组。只记录第一次出现的位置由于题目求的是最长长度同一个前缀和值出现多次时只有最早出现的位置才能贡献最长的子数组因此后续再遇到相同前缀和时不更新表中记录if prefix_sum not in prefix_map才写入。先查询、后写入对于每个位置必须先检查prefix_sum - k是否存在再记录当前prefix_sum的位置。如果顺序颠倒当k 0时会把刚写入的自身当作答案来源导致错误地算出长度为0的子数组。思路 1代码from typing import List class Solution: def maxSubArrayLen(self, nums: List[int], k: int) - int: if not nums: return 0 # 哈希表记录前缀和第一次出现的位置 prefix_map {0: -1} # 前缀和为0的位置为-1空数组 prefix_sum 0 max_length 0 for i in range(len(nums)): # 计算当前位置的前缀和 prefix_sum nums[i] # 检查是否存在前缀和 prefix_sum - k # 如果存在说明从 prefix_map[prefix_sum - k] 1 到 i 的子数组和为 k if prefix_sum - k in prefix_map: # 计算当前子数组的长度 current_length i - prefix_map[prefix_sum - k] max_length max(max_length, current_length) # 如果当前前缀和还没有记录则记录其位置 if prefix_sum not in prefix_map: prefix_map[prefix_sum] i return max_length思路 1复杂度分析时间复杂度$O(n)$其中 $n$ 是数组的长度。只需要遍历数组一次每次哈希表的查找和插入操作都是 $O(1)$。相比暴力枚举所有子数组的 $O(n^2)$这是能在 $2 \times 10^5$ 的数据规模下通过的方案。空间复杂度$O(n)$哈希表最多存储 $n$ 个不同的前缀和。逐步模拟以示例 1 验证算法以nums [1,-1,5,-2,3], k 3为例下表完整对应代码执行过程inums[i]prefix_sumprefix_sum - k 命中?长度prefix_map更新后初始—0——{0: -1}0111-3-2 未命中—{0: -1, 1: 0}1-100-3-3 未命中—{0: -1, 1: 0}0 已有不更新2555-32 未命中—{0: -1, 1: 0, 5: 2}3-233-30 命中位置 -13-(-1)4{0: -1, 1: 0, 5: 2, 3: 3}4366-33 命中位置 34-31{0: -1, 1: 0, 5: 2, 3: 3, 6: 4}遍历结束max_length 4对应子数组[1, -1, 5, -2]下标 03。注意第 1 行中prefix_sum 0再次出现时不更新记录保留位置 -1这正是「只记录首次出现位置」策略的体现。仓库中的姊妹题一个技巧四道变体本题属于「前缀和 哈希表」这一家族AlgoNote 仓库中收录了同一技巧下的多种变体适合对照学习、形成知识网络题目题解文档与本题的差异0560. 和为 K 的子数组subarray-sum-equals-k.md哈希表记录前缀和出现次数求的是和为 k 的子数组个数本题记录首次位置求最长长度0525. 连续数组contiguous-array.md把 1 记作 1、0 记作 -1构造「数量差」这一变种前缀和求差值为 0 的最长子数组——思路与本题几乎同构同样初始化{0: -1}0209. 长度最小的子数组minimum-size-subarray-sum.md元素全为正可用滑动窗口 O(n) 求解是本题「不能滑动窗口」的反面对照0303. 区域和检索range-sum-query-immutable.md用线段树/前缀和做静态区间和查询体现「子数组和 两个前缀和之差」在查询场景下的另一应用其中 0560. 和为 K 的子数组 与本题的代码结构几乎完全一致唯一区别是它用pre_dic[pre_sum] 1累计出现次数、count pre_dic[pre_sum - k]累加答案而 0525. 连续数组 则展示了「记录首次出现下标求最长」的同一模板在二进制数组上的迁移。建议读者将这三题0325 / 0560 / 0525放在一起对比记忆同一张哈希表记录「位置」还是「次数」决定了答案是「最长长度」还是「个数」。总结与延伸本质把「任意子数组的和」转化为「两个前缀和的差」配合哈希表在 O(1) 时间内反向查找所需的另一个前缀和是处理含负数数组的连续子数组求和问题的通用武器。两个必须记住的初始化与顺序约定哈希表初始化为{0: -1}处理从下标 0 开始的子数组每次迭代「先查询prefix_sum - k再写入prefix_sum」。复杂度红线$O(n)$ 时间、$O(n)$ 空间是本题的最终形态在nums.length高达 $2 \times 10^5$ 时任何 $O(n^2)$ 的暴力枚举都会超时。举一反三前缀和 哈希表还可用于「和为 k 的子数组个数」「0 和 1 数量相同的最长子数组」等题目相关完整题解均可在 docs/solutions 目录下按题号检索配合仓库中的题目总览 00_05_solutions_list.md 进行系统刷题。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 560 和为 K 的子数组题解前缀和 哈希表 O(n) 解法详解LeetCode 560 和为 K 的子数组题解前缀和 哈希表 O n 解法详解 本文基于本仓库 problems/560.subarray sum eq文档教程知识库AlgoNote 算法通关手册精讲LeetCode 0003 无重复字符的最长子串——哈希表 不定长滑动窗口AlgoNote 算法通关手册精讲LeetCode 0003 无重复字符的最长子串——哈希表 不定长滑动窗口 本文是「算法通关手册」AlgoNote 仓教程文档知识库LeetCode 560 Subarray Sum Equals K 题解前缀和 哈希表统计子数组和等于 k 的个数LeetCode 560 Subarray Sum Equals K 题解前缀和 哈希表统计子数组和等于 k 的个数 本篇技术指南围绕 LeetCode示例工程教程上一篇GitLab CI 项目推荐下一篇hudi-agent-gateway用单进程为 Hudi Lakehouse 提供 Agent 对话、MCP 工具与聊天 UI创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考