题目描述
思路解析动画文字版
记住这把钥匙:恰好 k 个 = atMost(k) − atMost(k−1)。下面先详细滑 atMost(2),再滑 atMost(1),最后相减。
先跑 atMost(2):统计「不同整数个数不超过 2」的子数组有多少个。右指针一格格扩,一旦不同数超过 2 就左缩,每步把「以右端点结尾的合法子数组个数」加进来。
右指针到第 0 位(值 1),窗口里不同整数变成 1 个。没超过 limit=2,窗口合法。
窗口 [0, 0] 合法,以第 0 位结尾、左端从 0 到 0 的子数组不同数都 ≤ 2,共 1 个,atMost(2) 加到 1。
右指针到第 1 位(值 2),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
窗口 [0, 1] 合法,以第 1 位结尾、左端从 0 到 1 的子数组不同数都 ≤ 2,共 2 个,atMost(2) 加到 3。
右指针到第 2 位(值 1),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
窗口 [0, 2] 合法,以第 2 位结尾、左端从 0 到 2 的子数组不同数都 ≤ 2,共 3 个,atMost(2) 加到 6。
右指针到第 3 位(值 2),窗口里不同整数变成 2 个。没超过 limit=2,窗口合法。
窗口 [0, 3] 合法,以第 3 位结尾、左端从 0 到 3 的子数组不同数都 ≤ 2,共 4 个,atMost(2) 加到 10。
右指针到第 4 位(值 3),窗口里不同整数变成 3 个。它 > limit=2(红),下一步要左缩。
不同数超了,左指针右移 3 步、把移出的数从计数里减掉,distinct 降回 2。现在窗口 [3, 4] 合法,以第 4 位结尾的合法子数组有 2 个,atMost(2) 加到 12。
这一趟扫完,不同整数不超过 2 的子数组共 12 个,记下 atMost(2) = 12。
接着跑 atMost(1):统计「不同整数个数不超过 1」的子数组有多少个。右指针一格格扩,一旦不同数超过 1 就左缩,每步把「以右端点结尾的合法子数组个数」加进来。
窗口 [0, 0] 合法,以第 0 位结尾、左端从 0 到 0 的子数组不同数都 ≤ 1,共 1 个,atMost(1) 加到 1。
不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [1, 1] 合法,以第 1 位结尾的合法子数组有 1 个,atMost(1) 加到 2。
不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [2, 2] 合法,以第 2 位结尾的合法子数组有 1 个,atMost(1) 加到 3。
不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [3, 3] 合法,以第 3 位结尾的合法子数组有 1 个,atMost(1) 加到 4。
不同数超了,左指针右移 1 步、把移出的数从计数里减掉,distinct 降回 1。现在窗口 [4, 4] 合法,以第 4 位结尾的合法子数组有 1 个,atMost(1) 加到 5。
这一趟扫完,不同整数不超过 1 的子数组共 5 个,记下 atMost(1) = 5。
两趟都跑完:atMost(2)=12、atMost(1)=5。相减 12−5=7,就是恰好含 2 个不同整数的子数组个数,和开头说的一致。
边界:题目保证 k ≥ 1(差分会用到 atMost(k−1),k=1 时退到合法的 atMost(0));k 超过不同数总量则返回 0。
面试常考:讲清差分为何成立,以及这是「恰好 → 两个至多」的通用套路。
参考代码
from typing import Listfrom collections import defaultdictclass 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)复杂度
- 时间：O(n)，atMost 跑两趟,每趟左右指针各前进一遍、每个元素进出窗口各一次
- 空间：O(U)，哈希表给每个出现过的不同整数留一个计数键(计数归零也没删键),最多 U 个不同值,U ≤ n
易错点
面试追问把动画讲成自己的话
追问atMost(k) − atMost(k−1) 为什么正好是「恰好 k 个」?
追问这个「至多 − 至多」的套路还能用在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计定界子数组的数目
LeetCode 2444 · 困难 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题