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

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

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

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

设前缀和为 pre[i]，若存在 pre[i] - pre[j] = k，则子数组 j+1..i 和为 k。

用哈希表记录每个前缀和的最早出现位置以获取最长长度。

遍历一次即可更新答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，哈希表存储前缀和。

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);

        int pre = 0;
        int ans = 0;

        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];

            if (!first.containsKey(pre)) {
                first.put(pre, i);
            }

            Integer idx = first.get(pre - k);
            if (idx != null) {
                ans = Math.max(ans, i - idx);
            }
        }

        return ans;
    }
}

func maxSubArrayLen(nums []int, k int) int {
	first := make(map[int]int)
	first[0] = -1

	pre := 0
	ans := 0

	for i, v := range nums {
		pre += v
		if _, ok := first[pre]; !ok {
			first[pre] = i
		}
		if idx, ok := first[pre-k]; ok {
			if i-idx > ans {
				ans = i - idx
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和
525. 连续数组	中等	前缀和
1248. 统计优美子数组	中等	前缀和
325. 和等于 k 的最长子数组长度	中等	前缀和
303. 区域和检索 - 数组不可变	简单	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/82000932