LeetCode 2461中等滑动窗口/哈希
长度为 K 子数组中的最大和 图解题解
这道题到底在问什么
给定整数数组 nums 和整数 k,返回长度为 k、且 k 个元素互不相同的连续子数组里的最大和;不存在则返回 0。
- 输入
- nums=[1,5,4,2,9,9,9], k=3
- 输出
- 15（[4,2,9] 和最大且互不相同）
- 输入
- nums=[4,4,4], k=3
- 输出
- 0（唯一窗口有重复）
最优解：一步一步想明白
- 3记住这把钥匙:定长窗口加右减左 O(1) 更新和;计数表里不同数的种数==3 才算「全不同」、才更新答案。
- 4先把最左、长度 3 的窗口建起来:第 0 位是 1,加进窗口和、计数表记一笔,现在窗口和是 1、有 1 种不同的数。
- 5先把最左、长度 3 的窗口建起来:第 1 位是 5,加进窗口和、计数表记一笔,现在窗口和是 6、有 2 种不同的数。
- 6先把最左、长度 3 的窗口建起来:第 2 位是 4,加进窗口和、计数表记一笔,现在窗口和是 10、有 3 种不同的数。
- 7第一个长度 3 的窗口 [1, 5, 4] 建好了,和是 10。计数表里有 3 种不同的数,正好等于 3,说明全不同,把它当作目前最大和 ans = 10。
- 8窗口右滑一格。先把右边新进来的 nums[3] = 2 计入:窗口和暂时变成 12,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。
- 9再把左边移出的 nums[0] = 1 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [5, 4, 2] 的和是 11。下一步看这 3 个数有没有重复。
- 10判一下:计数表里有 3 种不同的数,正好 3 种、全不同,而且和 11 比之前的 ans 还大,刷新 ans = 11。
- 11窗口接着右移。先把右边新进来的 nums[4] = 9 计入:窗口和暂时变成 20,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。
- 12再把左边移出的 nums[1] = 5 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [4, 2, 9] 的和是 15。下一步看这 3 个数有没有重复。
- 13判一下:计数表里有 3 种不同的数,正好 3 种、全不同,而且和 15 比之前的 ans 还大,刷新 ans = 15。
- 14再滑一格。先把右边新进来的 nums[5] = 9 计入:窗口和暂时变成 24,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。
- 15再把左边移出的 nums[2] = 4 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [2, 9, 9] 的和是 20。下一步看这 3 个数有没有重复。
- 16判一下:计数表里有 2 种不同的数,不到 3 种,说明有重复(红色标出的就是重复的那些位置),这个窗口不算、直接跳过。
- 17窗口继续右滑。先把右边新进来的 nums[6] = 9 计入:窗口和暂时变成 29,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。
- 18再把左边移出的 nums[3] = 2 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [9, 9, 9] 的和是 27。下一步看这 3 个数有没有重复。
- 19判一下:计数表里有 1 种不同的数,不到 3 种,说明有重复(红色标出的就是重复的那些位置),这个窗口不算、直接跳过。
- 20滑完全程,和最大的那个「k 个互不相同」窗口是 [4, 2, 9],和正好是 15,这就是答案。回头看,我们没给任何窗口重新求和,全靠「加右减左」O(1) 更新,再用计数表的种数判全不同。
⚠️ 容易写错的地方
✗ 错：每个窗口重新求和、重新去重
✓ 对：加右减左 O(1) 更新 cur,计数表增量维护
重算是 O(n·k),增量滑动是 O(n)
✗ 错：用「窗口长度」判全不同
✓ 对：看计数表里不同数的种数是否 == k
长度永远是 k,真正能反映「有没有重复」的是不同值的种数
✗ 错：计数减到 0 不删键
✓ 对：某个数计数归零必须从表里删掉
不删的话 count 的大小会虚高,判全不同就错了
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import defaultdict
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
count = defaultdict(int)
cur = ans = 0
for right, x in enumerate(nums):
count[x] += 1
cur += x
if right >= k:
y = nums[right - k]
cur -= y
count[y] -= 1
if count[y] == 0:
del count[y]
if right >= k - 1 and len(count) == k:
ans = max(ans, cur)
return ansC++
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
unordered_map<int,int> count;
long long cur = 0, ans = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
count[nums[right]]++;
cur += nums[right];
if (right >= k) {
int y = nums[right - k];
cur -= y;
if (--count[y] == 0) count.erase(y);
}
if (right >= k - 1 && (int)count.size() == k) ans = max(ans, cur);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
long cur = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
cur += nums[right];
if (right >= k) {
int y = nums[right - k];
cur -= y;
count.put(y, count.get(y) - 1);
if (count.get(y) == 0) count.remove(y);
}
if (right >= k - 1 && count.size() == k) ans = Math.max(ans, cur);
}
return ans;
}
}复杂度
时间
O(n)
每个元素进窗口、出窗口各一次,计数表加删都是均摊 O(1)
空间
O(k)
计数表里最多同时存窗口内的 k 个不同的数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 长度为 K 子数组中的最大和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用定长滑窗而不是可变滑窗?+
因为窗口长度被题目钉死为 k,不需要左指针根据条件伸缩。这是「定长窗口」标准模板:先建第一个窗口,再整体右移,每移一格做一次「加右减左」的 O(1) 更新,顺带维护一张计数表判重。
如果不要求互不相同,只求长度 k 最大和呢?+
那就更简单,去掉计数表、只留 cur 的加右减左,每个定长窗口都参与取最大即可。本题的「互不相同」约束,正是靠计数表的种数 == k 这一个判断加上去的。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 长度为 K 子数组中的最大和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。