LeetCode 325. 和等于 k 的最长子数组长度

约 6 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 华为 拼多多 虾皮
标签
数组 哈希表 前缀和
目录

题目描述

✅ 325. 和等于 k 的最长子数组长度

image-20250418171419093

题意分析

给定整数数组 nums 和目标值 k，要在所有连续子数组里挑出「和恰好等于 k」的那些，返回其中最长的长度；一个都不存在时返回 0。注意要的是长度这个标量，不是下标区间，也不是方案数。

「连续」这个词把候选集合从指数级压到了 $O(n^2)$ 个区间，也意味着任何一段候选都能用左右两个端点唯一描述。$n$ 可以到 $10^5$ 量级，逐对枚举端点是 $10^{10}$ 次运算，必然超时，所以只能扫一遍数组、在扫的过程中把「以当前位置结尾的最优答案」直接问出来。

约束里最关键的一条是 nums 可以含负数与 0。这一条直接掐死了「右端点右移则区间和单调增」这个前提，也就掐死了双指针伸缩窗口的正确性：窗口和大于 k 时收缩左边界，未必能让和变小，反而可能因为丢掉一个负数而变大。凡是区间和在负数下不再单调的题，都必须换成「把前缀信息存起来，用差值反查」的思路。

边界要盯住三处：子数组必须非空，长度至少为 1；答案可能从下标 0 开始，这段区间没有「前一个位置」可以配对，需要一个虚拟的起点；k 本身可以是 0 或负数，元素也可以是 0，所以不能用「和为 0 就跳过」之类的假设去剪枝。另外整数累加可能超出 32 位范围，累加变量的类型要想清楚。

解法：前缀和 + 最早位置哈希表

核心思路

记 prefix 为当前位置之前所有元素的和。若子数组 nums[left..right] 的和为 k，则：

prefix[right + 1] - prefix[left] = k

因而扫描到 right 时，只需在历史前缀和中查找 prefix[right + 1] - k。数组含负数，区间和不随窗口伸缩而单调，所以滑动窗口不成立；哈希表可以在均摊 $O(1)$ 时间完成这次查找。

哈希表记录 前缀和 → 最早出现位置。固定 right 后，合法区间长度为 right - leftPrefixIndex，左侧前缀位置越早，区间越长。因此同一个前缀和后续再出现时绝不能覆盖最早位置。

预置 0 → -1 表示数组开始前的空前缀，使从下标 0 开始的区间也能套用同一公式。

正确性依据：遍历到每个右端点时，算法准确查询使区间和为 k 的唯一目标前缀和值；该值的最早位置又给出以当前点结尾的最长合法区间。对所有右端点取最大值，就覆盖并选出了全局最长答案。

解题步骤

  1. 初始化哈希表 firstIndex，放入空前缀 0 → -1，答案为 0。
  2. 从左到右累加当前前缀和 prefixSum。
  3. 查询 prefixSum - k 的最早位置；若存在，用 i - index 更新最长长度。
  4. 用 putIfAbsent 记录当前前缀和，已经出现过则保留旧位置。
  5. 扫描结束后返回答案。

以 nums = [1, -1, 5, -2, 3]、k = 3 为例：遍历到下标 1 时前缀和再次为 0，仍保留最早位置 -1；到下标 3 时前缀和为 3，查到目标前缀和 0，长度是 3 - (-1) = 4，对应 [1, -1, 5, -2]。若把 0 的位置覆盖成 1，这里只能得到长度 2。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Long, Integer> firstIndex = new HashMap<>();
        firstIndex.put(0L, -1);
        long prefixSum = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            Integer left = firstIndex.get(prefixSum - k);
            if (left != null) {
                ans = Math.max(ans, i - left);
            }
            firstIndex.putIfAbsent(prefixSum, i);
        }
        return ans;
    }
}

func maxSubArrayLen(nums []int, k int) int {
    firstIndex := map[int64]int{0: -1}
    var prefixSum int64
    target := int64(k)
    ans := 0
    for i, num := range nums {
        prefixSum += int64(num)
        if idx, ok := firstIndex[prefixSum-target]; ok {
            if i-idx > ans {
                ans = i - idx
            }
        }
        if _, ok := firstIndex[prefixSum]; !ok {
            firstIndex[prefixSum] = i
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：平均 $O(n)$。数组只扫描一次，每轮进行常数次哈希表操作。
  • 空间复杂度：$O(n)$。最坏情况下，n + 1 个前缀和互不相同，都需要记录。

关键点总结

  • 含负数时区间和没有单调性，不能使用普通滑动窗口。
  • 前缀和把区间条件转成一次差值查询：当前前缀和减去 k。
  • 求最长就保存最早下标；若题目改成统计个数，则应保存出现次数，不能沿用本题写法。
  • 0 → -1 统一处理从数组开头出发的区间，也使长度公式始终是 i - index。
  • 查询放在写入当前前缀之前，语义上只让当前右端点与历史前缀配对，排除空区间。

易错点总结

  • 覆盖最早位置：[1, -1, 5, -2, 3]、k = 3 中，若把前缀和 0 的位置从 -1 覆盖成 1，答案会从 4 变成 2。
  • 遗漏 0 → -1：会漏掉所有从下标 0 开始的答案；[1, 2]、k = 3 应返回 2。
  • 长度多加 1：哈希表存的是左侧前缀结束位置，合法长度已经是 i - index。
  • 对含负数数组使用滑动窗口：移除一个负数会让窗口和增大，无法根据当前和决定移动哪一侧。
  • 每次命中立即返回：当前只是以某个右端点结尾的最优区间，后面仍可能出现更长答案。
  • 前缀和使用过窄类型：大量大整数相加可能溢出；实现使用 long / int64 保存前缀和与哈希键。

相似题目

题目 难度 考察点
560. 和为 K 的子数组 中等 求方案数而非最长，哈希表存的是前缀和的出现次数，命中时累加计数
525. 连续数组 中等 把 0 映射成 -1 转化为和为 0 的最长子数组，与本题同框架但需先做变换
974. 和可被 K 整除的子数组 中等 键换成前缀和对 K 取模的余数，还要处理负数取模归一化
930. 和相同的二元子数组 中等 元素非负，除哈希表外还可用两个滑动窗口相减，正好反衬本题为何不行
1074. 元素和为目标值的子矩阵数量 困难 二维版本，枚举上下边界压成一维后再套本题的哈希表反查
209. 长度最小的子数组 中等 元素全正使区间和单调，反而应该用滑动窗口，是本题判据的对照组
437. 路径总和 III 中等 前缀和搬到树上，回溯时必须撤销当前节点对哈希表的贡献
面试题 17.05. 字母与数字 中等 字母记 +1、数字记 -1，求最长平衡段，还需返回具体子数组而非长度
LCR 011. 连续数组 中等 与 525 同题，可直接套用本题保留最早下标的写法
LCR 010. 和为 K 的子数组 中等 与 560 同题，注意计数版不能沿用「只保留最早位置」的剪枝