K 个不同整数的子数组 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,1,2,3], k=2
- 输出
- 7
最优解：一步一步想明白
- 3记住这把钥匙:恰好 k 个 = atMost(k) − atMost(k−1)。下面先详细滑 atMost(2),再滑 atMost(1),最后相减。
- 4先跑 atMost(2):统计「不同整数个数不超过 2」的子数组有多少个。右指针一格格扩,一旦不同数超过 2 就左缩,每步把「以右端点结尾的合法子数组个数」加进来。
- 5右指针到第 0 位(值 1),窗口里不同整数变成 1 个。没超过 limit=2,窗口合法。
- 6窗口 [0, 0] 合法,以第 0 位结尾、左端从 0 到 0 的子数组不同数都 ≤ 2,共 1 个,atMost(2) 加到 1。
- 7右指针到第 1 位(值 2),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
- 8窗口 [0, 1] 合法,以第 1 位结尾、左端从 0 到 1 的子数组不同数都 ≤ 2,共 2 个,atMost(2) 加到 3。
- 9右指针到第 2 位(值 1),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
- 10窗口 [0, 2] 合法,以第 2 位结尾、左端从 0 到 2 的子数组不同数都 ≤ 2,共 3 个,atMost(2) 加到 6。
- 11右指针到第 3 位(值 2),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
- 12窗口 [0, 3] 合法,以第 3 位结尾、左端从 0 到 3 的子数组不同数都 ≤ 2,共 4 个,atMost(2) 加到 10。
- 13右指针到第 4 位(值 3),窗口里不同整数变成 3 个。它 > limit=2(红),下一步要左缩。
- 14不同数超了,左指针右移 3 步、把移出的数从计数里减掉,distinct 降回 2。现在窗口 [3, 4] 合法,以第 4 位结尾的合法子数组有 2 个,atMost(2) 加到 12。
- 15这一趟扫完,不同整数不超过 2 的子数组共 12 个,记下 atMost(2) = 12。
- 16接着跑 atMost(1):统计「不同整数个数不超过 1」的子数组有多少个。右指针一格格扩,一旦不同数超过 1 就左缩,每步把「以右端点结尾的合法子数组个数」加进来。
- 17窗口 [0, 0] 合法,以第 0 位结尾、左端从 0 到 0 的子数组不同数都 ≤ 1,共 1 个,atMost(1) 加到 1。
- 18不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [1, 1] 合法,以第 1 位结尾的合法子数组有 1 个,atMost(1) 加到 2。
- 19不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [2, 2] 合法,以第 2 位结尾的合法子数组有 1 个,atMost(1) 加到 3。
- 20不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [3, 3] 合法,以第 3 位结尾的合法子数组有 1 个,atMost(1) 加到 4。
- 21不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [4, 4] 合法,以第 4 位结尾的合法子数组有 1 个,atMost(1) 加到 5。
- 22这一趟扫完,不同整数不超过 1 的子数组共 5 个,记下 atMost(1) = 5。
- 23两趟都跑完:atMost(2)=12、atMost(1)=5。相减 12−5=7,就是恰好含 2 个不同整数的子数组个数,和开头说的一致。
⚠️ 容易写错的地方
✗ 错：直接对「恰好 k 个」滑窗
✓ 对：转成 atMost(k) − atMost(k−1)
「恰好」窗口合法性不单调、没法稳定伸缩;「至多」单调才能滑
✗ 错：每步只加 1 个
✓ 对：每步加 right − left + 1 个
以 right 结尾、左端从 left 到 right 的子数组都满足「≤ limit」,是一整批
✗ 错：忘了减 atMost(k−1)
✓ 对：两趟都要跑、最后相减
只算 atMost(k) 会把「不到 k 个」的也算进去,必须扣掉
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import defaultdict
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def at_most(limit):
count = defaultdict(int)
left = ans = distinct = 0
for right, x in enumerate(nums):
if count[x] == 0:
distinct += 1
count[x] += 1
while distinct > limit:
count[nums[left]] -= 1
if count[nums[left]] == 0:
distinct -= 1
left += 1
ans += right - left + 1
return ans
return at_most(k) - at_most(k - 1)C++
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
int atMost(vector<int>& nums, int limit) {
unordered_map<int,int> count;
int left = 0, distinct = 0, ans = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
if (count[nums[right]]++ == 0) distinct++;
while (distinct > limit) if (--count[nums[left++]] == 0) distinct--;
ans += right - left + 1;
}
return ans;
}
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
};Java
import java.util.*;
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return atMost(nums, k) - atMost(nums, k - 1);
}
private int atMost(int[] nums, int limit) {
Map<Integer, Integer> count = new HashMap<>();
int left = 0, distinct = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
if (count.get(nums[right]) == 1) distinct++;
while (distinct > limit) {
count.put(nums[left], count.get(nums[left]) - 1);
if (count.get(nums[left]) == 0) distinct--;
left++;
}
ans += right - left + 1;
}
return ans;
}
}复杂度
时间
O(n)
atMost 跑两趟,每趟左右指针各前进一遍、每个元素进出窗口各一次
空间
O(U)
哈希表给每个出现过的不同整数留一个计数键(计数归零也没删键),最多 U 个不同值,U ≤ n
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 K 个不同整数的子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
atMost(k) − atMost(k−1) 为什么正好是「恰好 k 个」?+
atMost(k) 数的是「不同数 ≤ k」的子数组(含 0、1、…、k 个不同的);atMost(k−1) 数的是「不同数 ≤ k−1」的(含 0、…、k−1 个的)。两者相减,「≤ k−1 个」的部分被消掉,只剩「不同数正好等于 k」的,所以差就是恰好 k 个。
这个「至多 − 至多」的套路还能用在哪?+
凡是「恰好 k 个 X」的计数题,只要「至多 k 个 X」这个量随窗口单调,都能这么拆。最稳的例子是「恰好 k 个奇数的子数组」(奇数个数随窗口扩大只增不减)。要小心的是「和为某值的子数组个数」:只有在数组非负、窗口和单调时才适用,一旦有负数、和不再单调,这套「至多」差分就失效了,得改用前缀和加哈希。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 K 个不同整数的子数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。