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

2026-09-29 HGNULB 约 5 分钟

文章信息 15 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决会员题 5-10 字节华为美团拼多多小米快手携程 B站虾皮

题目描述

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

给定一个整数数组 nums 和一个整数 k，找出数组中和等于 k 的最长连续子数组的长度。如果不存在符合条件的子数组，返回 0。

示例 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。

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
-10^9 <= k <= 10^9

题意分析

求和恰好为 k 的最长连续子数组长度，没有符合条件的非空区间时返回 0。数组允许负数与零，扩大窗口不一定让和增大，缩小窗口也不一定让和减小，因此不能根据当前和与 k 的大小关系移动窗口。

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

核心思路

[!blue]

设 P(i) 为 nums[0..i] 的和。区间 nums[j+1..i] 的和等于 P(i)-P(j)，要使它恰好为 k，就需要 P(j)=P(i)-k。所以每处理一个右端点 i，只需查询之前是否出现过目标前缀和 prefixSum-k。

firstIndex 保存每个前缀和最早出现的结束下标。固定右端点后，合法区间长度是 i-j；相同前缀和中，越早的 j 形成的区间越长，较晚的位置对当前和未来的右端点都不会更优。因此每个前缀和只登记第一次出现的位置。

空前缀的和为 0，结束下标记作 -1，预先存入 0 -> -1。这样从数组开头开始的区间也能通过相同查询得到长度 i+1。每个右端点都计算自己的最长合法区间，再取其中最大值，就覆盖了所有可能的答案。

解题步骤

初始化哈希表 firstIndex，放入空前缀 0 → -1，答案为 0。

从左到右累加当前前缀和 prefixSum。

查询 prefixSum - k 的最早位置；若存在，用 i - index 更新最长长度。

用 putIfAbsent 记录当前前缀和，已经出现过则保留旧位置。

扫描结束后返回答案；从未找到目标前缀时，答案保持为 0。

查询先于登记，保证配对的前缀来自当前位置之前。k = 0 时查找的虽然正是当前前缀和值，但必须使用它之前的出现位置，才能得到非空区间。

代码实现

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 个前缀和互不相同，都需要记录。

关键点总结

[!green]

前缀和相减只依赖加法关系，对正数、负数和零都成立。

哈希表的值是最早结束下标，既用于算长度，也避免保留无用的较晚位置。

ans 是已经处理过的所有右端点的最优答案，不能在第一次命中时返回。

易错点总结

[!yellow]

覆盖最早位置：相同前缀和换成更晚的位置，会缩短后续候选区间。

遗漏 0 → -1：会漏掉从下标 0 开始的合法区间。

长度多加 1：哈希表存的是左侧前缀结束位置，合法长度已经是 i - index。

对含负数数组使用滑动窗口：移除一个负数会让窗口和增大，无法根据当前和决定移动哪一侧。

用出现次数代替位置：次数能帮助统计区间个数，但不能给出区间长度。

相似题目

题目	难度	关联与区别
560. 和为 K 的子数组	中等	同样查询prefix-k，原题保存频次计数量，本题保存最早位置求最大长度。
525. 连续数组	中等	把0映射成-1后，等量01区间就是和为0的特例，同样保留最早前缀位置。
437. 路径总和 III	中等	前缀和配合哈希表查找所需历史前缀；本题存最早前缀下标以最大化长度，该题沿树路径维护前缀次数并回溯恢复。
930. 和相同的二元子数组	中等	前缀和配合哈希表查找所需历史前缀；本题存最早前缀下标以最大化长度，该题二进制数组上统计目标和。
1248. 统计「优美子数组」	中等	前缀和配合哈希表查找所需历史前缀；本题存最早前缀下标以最大化长度，该题把奇数映射为 1 后统计精确数量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/82000932

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！