AlgoNote「算法通关手册」精讲：0325. 和等于 k 的最长子数组长度——前缀和 + 哈希表的 O(n) 解法

• 教程
• 文档
• 知识库

本文是 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：前缀和 + 哈希表

核心推导：把子数组和变成前缀和之差

1. 计算前缀和：定义 $prefix_sum[i]$ 表示数组前 $i$ 个元素的和，即 $$prefix_sum[i] = \sum_{j=0}^{i-1} nums[j]$$ 它可以通过递推得到：$prefix_sum[i] = prefix_sum[i-1] + nums[i-1]$。

2. 利用前缀和性质：对于子数组 $nums[i:j+1]$（即下标区间 $[i, j]$），其和为 $$prefix_sum[j+1] - prefix_sum[i]$$ 如果这个和等于 $k$，则有 $$prefix_sum[j+1] - prefix_sum[i] = k$$ 移项得： $$prefix_sum[i] = prefix_sum[j+1] - k$$

   也就是说：当我们站在位置 $j+1$，只要历史上出现过前缀和等于 $prefix_sum[j+1] - k$，那么从该历史位置到当前位置之间的子数组和就恰好等于 $k$。

3. 哈希表记录首次出现位置：使用哈希表prefix_map记录每个前缀和第一次出现的位置。遍历到当前位置时，若prefix_sum - k已存在于表中，说明存在一个和为 $k$ 的子数组。

4. 更新最长长度：每次找到满足条件的子数组时，用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为例（下表完整对应代码执行过程）：

遍历结束，max_length = 4，对应子数组[1, -1, 5, -2]（下标 0～3）。注意第 1 行中prefix_sum = 0再次出现时不更新记录（保留位置 -1），这正是「只记录首次出现位置」策略的体现。

仓库中的姊妹题：一个技巧，四道变体

本题属于「前缀和 + 哈希表」这一家族，AlgoNote 仓库中收录了同一技巧下的多种变体，适合对照学习、形成知识网络：

其中 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 进行系统刷题。

• 教程
• 文档
• 知识库