LeetCode 325和等于 K 的最长子数组长度 | 哈希表记录前缀和首次出现位置引言和等于 K 的最长子数组长度Maximum Size Subarray Sum Equals K是 LeetCode 第 325 题难度为 Medium。题目要求在整数数组中找到连续子数组的和等于 K 的最长长度返回这个最长长度。这是一个经典的前缀和与哈希表结合的问题在实际应用中有广泛的应用场景。这个问题展示了前缀和技巧与哈希表结合的威力。通过记录每个前缀和首次出现的索引我们可以在 O(n) 时间内找到以当前索引结尾且和等于 K 的最长子数组。这种边走边查的思路是解决子数组和问题的通用范式。问题分析题目描述给定一个整数数组 nums 和一个整数 K找到连续子数组 nums[i:j]包含 i 到 j 的元素的和等于 K 的最长长度。如果不存在这样的子数组返回 0。例如输入 nums [1, -1, 5, -2, 3]K 3最长子数组是 [1, -1, 5, -2]长度为 4其和为 3。又如输入 nums [-2, -1, 2, 1]K 1最长子数组是 [-1, 2]长度为 2其和为 1。问题特点这道题的核心挑战在于如何高效地找到和为 K 的子数组。如果使用暴力枚举所有子数组时间复杂度为 O(n²)。如果使用前缀和加双指针滑动窗口虽然对于正数数组是 O(n)但对于包含负数的数组则不适用因为双指针无法处理负数的情况。哈希表方法的核心思想是使用前缀和来快速计算任意子数组的和。对于子数组 nums[i:j]包含 i 到 j其和等于 prefixSum[j1] - prefixSum[i]其中 prefixSum[k] 表示 nums[0:k] 的和。如果我们想知道是否存在子数组以 j 结尾且和等于 K就等价于检查 prefixSum[i] 是否等于 prefixSum[j1] - K。为什么用哈希表哈希表的作用是存储每个前缀和首次出现的索引。当我们遍历到索引 j 时对于每个可能的起点 i0 i j如果 prefixSum[i] prefixSum[j1] - K那么以 i 为起点的子数组和就等于 K。我们需要找到最小的 i即最长的子数组使得上述等式成立。哈希表可以帮助我们快速查找如果 prefixSum[j1] - K 存在于哈希表中说明存在一个起点 i 使得子数组和为 K。由于哈希表存储的是每个前缀和首次出现的索引我们用当前 j 减去首次出现位置就得到了最长子数组的长度。前缀和与哈希表结合前缀和概念前缀和是一个非常有用的技巧可以快速计算任意子数组的和。定义 prefixSum[0] 0prefixSum[i] nums[0] nums[1] ... nums[i-1]前 i 个元素的和。则子数组 nums[i:j]包含 i 到 j的和等于 prefixSum[j1] - prefixSum[i]。前缀和的优点在于将子数组和的计算从 O(n) 降低到 O(1)。在遍历数组的过程中我们可以动态计算前缀和而不需要事先存储所有前缀和。哈希表记录首次出现def maxSubArrayLen(nums, k): prefix_sum 0 max_len 0 first_occurrence {0: -1} for i, num in enumerate(nums): prefix_sum num if prefix_sum not in first_occurrence: first_occurrence[prefix_sum] i target prefix_sum - k if target in first_occurrence: max_len max(max_len, i - first_occurrence[target]) return max_len这段代码展示了前缀和与哈希表结合的完整实现。哈希表 first_occurrence 存储每个前缀和首次出现的索引初始化为 {0: -1}表示空子数组的前缀和为 0出现在索引 -1即数组开头之前。当遍历到索引 i 时首先更新前缀和 prefix_sum。然后如果当前前缀和不在哈希表中首次出现将其存入哈希表注意存储的是当前索引 i。接下来计算目标前缀和 target prefix_sum - k如果 target 在哈希表中说明存在以当前索引 i 结尾且和为 K 的子数组其长度为 i - first_occurrence[target]。最后更新最大长度。为什么只记录首次出现只记录每个前缀和首次出现的位置是为了获得最长的子数组。当我们从左到右遍历时对于相同的前缀和越早出现的位置距离当前索引越远子数组就越长。因此我们只需要记录每个前缀和首次出现的位置。算法正确性证明关键引理对于任意索引 j0 j n如果存在起点 i 使得子数组 nums[i:j] 的和等于 K那么 prefixSum[j1] - prefixSum[i] K即 prefixSum[i] prefixSum[j1] - K。反之如果存在索引 i 使得上述等式成立那么以 i 为起点的子数组和等于 K。这个引理是算法正确性的基础。它将是否存在和为 K 的子数组的问题转化为是否存在两个相同的前缀和而后者可以通过哈希表在 O(1) 时间内判断。最优性证明为什么只记录首次出现就能保证找到最长的子数组考虑索引 j 处的最长子数组即最小的 i 使得 prefixSum[i] prefixSum[j1] - K。由于我们从左到右遍历在索引 j 处first_occurrence[prefixSum[j1] - K] 存储的是满足条件的最小索引 i。因此j - i 就是以 j 结尾的最长子数组长度。代码实现Python 实现def maxSubArrayLen(nums, k): prefix_sum 0 max_len 0 first_occurrence {0: -1} for i, num in enumerate(nums): prefix_sum num if prefix_sum not in first_occurrence: first_occurrence[prefix_sum] i target prefix_sum - k if target in first_occurrence: max_len max(max_len, i - first_occurrence[target]) return max_lenJava 实现public int maxSubArrayLen(int[] nums, int k) { MapInteger, Integer firstOccurrence new HashMap(); firstOccurrence.put(0, -1); int prefixSum 0; int maxLen 0; for (int i 0; i nums.length; i) { prefixSum nums[i]; if (!firstOccurrence.containsKey(prefixSum)) { firstOccurrence.put(prefixSum, i); } int target prefixSum - k; if (firstOccurrence.containsKey(target)) { maxLen Math.max(maxLen, i - firstOccurrence.get(target)); } } return maxLen; }复杂度分析时间复杂度时间复杂度为 O(n)其中 n 是数组长度。我们只遍历数组一次每次循环执行常数次哈希表操作查找和插入这些都是 O(1) 的平均时间。空间复杂度空间复杂度为 O(n)最坏情况下需要存储 n1 个不同的前缀和加上初始的 0。空间主要用于哈希表 first_occurrence。边界情况处理空数组当数组为空时显然不存在子数组应该返回 0。外层循环不会执行max_len 保持为 0正确。全负数数组算法同样适用于包含负数的数组。前缀和技巧对正负数都适用哈希表方法也不受元素符号影响。全零数组对于全零数组如 [0, 0, 0] 和 K 0最长子数组长度是 3。算法会正确处理每次遍历时prefix_sum 总是 0first_occurrence[0] 保持为 -1target 0每次都会更新 max_len 为 i - (-1) i 1最后返回 3。K 为零K 可以为零此时我们需要找到和为零的最长子数组。算法同样适用因为我们在初始化哈希表时已经包含了 {0: -1}。只有负数没有正数算法同样适用因为前缀和可以递增也可以递减哈希表查找没有额外限制。变种问题和至少为 K 的最长子数组如果问题改为找到和至少为 K 的最长子数组算法需要稍作修改。我们不再检查 prefix_sum - k 是否存在而是检查 prefix_sum - k 0 是否成立这需要额外的数据结构如平衡 BST 来处理范围查询。计数问题如果问题改为计算和等于 K 的子数组数量而不是最长长度我们只需要将哈希表中的值从首次出现索引改为出现次数def count_subarrays(nums, k): prefix_sum 0 count 0 frequency {0: 1} for num in nums: prefix_sum num count frequency.get(prefix_sum - k, 0) frequency[prefix_sum] frequency.get(prefix_sum, 0) 1 return count和为 K 的最短子数组如果问题改为找到和等于 K 的最短子数组思路类似但哈希表需要存储每个前缀和的最后一次出现位置而不是首次这样才能得到最短子数组def shortest_subarray(nums, k): prefix_sum 0 min_len float(inf) last_occurrence {0: -1} for i, num in enumerate(nums): prefix_sum num if prefix_sum not in last_occurrence: last_occurrence[prefix_sum] i target prefix_sum - k if target in last_occurrence: min_len min(min_len, i - last_occurrence[target]) return min_len if min_len ! float(inf) else -1测试用例def test_max_sub_array_len(): assert maxSubArrayLen([1, -1, 5, -2, 3], 3) 4 assert maxSubArrayLen([-2, -1, 2, 1], 1) 2 assert maxSubArrayLen([], 0) 0 assert maxSubArrayLen([1], 0) 0 assert maxSubArrayLen([1], 1) 1 assert maxSubArrayLen([0, 0, 0, 0], 0) 4 assert maxSubArrayLen([-1, 2, -2, 3], 3) 2 assert maxSubArrayLen([1, 2, 3, -3, 1, 1, 1, -1, -2, -2], 3) 6 print(所有测试用例通过)实际应用场景子数组和问题在现实中有很多应用。在金融领域可以用来检测连续交易日使累计涨跌达到特定值。在信号处理中可以用来检测满足特定能量阈值的信号段。在文本处理中可以用来查找满足特定字符数差异的子串。前缀和与哈希表的结合是处理子数组和问题的通用范式。掌握这个技巧后可以解决很多类似的问题如股票最大利润实际上是子数组差的最大值、数组方差计算涉及平方和等。总结和等于 K 的最长子数组长度问题展示了前缀和与哈希表结合的威力。通过记录每个前缀和首次出现的位置我们可以在 O(n) 时间内解决看似需要 O(n²) 的问题。这种边走边查的思路是解决子数组和问题的经典范式。本题的关键洞察是子数组和等于 K 等价于两个前缀和的差等于 K。通过哈希表快速查找满足条件的两个前缀和我们可以高效地找到所有可能的子数组并记录最长长度。希望通过本文的讲解读者能够深入理解前缀和与哈希表结合的思想并将其应用到更多类似问题的解决中。