左神做法的理論依據
我們可以通過 集合的包含關系 和 具體示例枚舉 來直觀理解這一推導過程。以下結合題目示例 1 進行詳細說明：
示例 1 分析
輸入：nums = [1,2,1,2,3], k = 2
目標：計算恰好包含 2 種不同整數 的子數組個數。
步驟一集合 A 的計數
滑動窗口的核心邏輯是：
- 對于每個右邊界
r，找到最小左邊界l，使得窗口[l, r]內不同整數個數 ≤k。 - 此時，左邊界可以是
[l, r]中的任意位置，因此貢獻r - l + 1個子數組。
以示例 1 為例，滑動窗口計算 findNumsofMost(nums, 2)（即 |A|）的過程如下：
| r | 元素 | 窗口內元素 | 不同數 | 最小左邊界 l | 貢獻子數組數 |
|---|---|---|---|---|---|
| 0 | 1 | [1] | 1 | 0 | 1 |
| 1 | 2 | [1,2] | 2 | 0 | 2 |
| 2 | 1 | [1,2,1] | 2 | 0 | 3 |
| 3 | 2 | [1,2,1,2] | 2 | 0 | 4 |
| 4 | 3 | [2,1,2,3] | 3（超過 2） | 移動 l 到 1 | 窗口 [1,4] 含 2,1,3（3 種，仍超過）→ 繼續移動 l 到 2 → 窗口 [2,4] 含 1,2,3（3 種，仍超過）→ 移動 l 到 3 → 窗口 [3,4] 含 2,3（2 種）→ 最小 l=3，貢獻 (4-3+1=2) |
累加結果：(1+2+3+4+2=12)，即 |A|=12。
而 findNumsofMost(nums, 1)（即 |B|）的計算結果為 5（僅含單個元素的子數組），因此：
步驟 2：定義集合 B（不超過 k-1 種）
集合 B 包含所有不同整數個數 ≤1 的子數組（即僅含 1 種整數）。
枚舉所有滿足條件的子數組：
- 單個元素：
[1], [2], [1], [2], [3]，共 5 個。 - 連續相同元素的子數組：
[1]（位置 0）、[2]（位置 1）、[1]（位置 2）、[2]（位置 3）、[3]（位置 4）。- 無長度 ≥2 的連續相同元素（因為數組中相鄰元素不同）。
- 集合 B 的總數：5 個。
步驟 3：計算集合差集 A - B
根據定義：
恰好含 k 種的子數組個數 = |A| - |B|
-
集合 A 包含 含 1 種或 2 種 的子數組。
-
集合 B 包含 僅含 1 種 的子數組。
-
因此，A - B 即為僅含 2 種的子數組，其數量為：
|A| - |B| = 12 - 5 = 7這與題目示例 1 的輸出一致。
數學推導：集合差集的嚴格性
-
設 (f(m)) 表示 不同整數個數 ≤m 的子數組個數。
-
恰好含 k 種的子數組必須滿足：
- 不同整數個數 ≤k（屬于集合 A），
- 且不同整數個數 >k-1（不屬于集合 B）。
-
因此，恰好含 k 種的子數組是 A 中排除 B 的部分，即：
= f(k) - f(k-1)
例子 2：更簡單的數組（nums = [1,1,2], k=2）
為了更直觀，我們用一個更短的數組驗證。
問題目標
找到所有「恰好有 2 種不同整數」的子數組。
數組分析
數組 [1,1,2] 的所有子數組及其不同整數個數：
| 子數組 | 內容 | 不同整數個數 |
|---|---|---|
| [0,0] | [1] | 1 |
| [0,1] | [1,1] | 1 |
| [0,2] | [1,1,2] | 2 |
| [1,1] | [1] | 1 |
| [1,2] | [1,2] | 2 |
| [2,2] | [2] | 1 |
集合 A（≤2）和 B（≤1）的大小
- 集合 A（≤2）：所有子數組都滿足（因為最大不同個數是 2），共 6 個。
- 集合 B（≤1）：不同整數個數為 1 的子數組，即
[0,0], [0,1], [1,1], [2,2]→ 共 4 個。
結論驗證
恰好有 2 種不同整數的子數組是 [0,2], [1,2] → 共 2 個。
根據公式 |A| - |B| = 6 - 4 = 2，與實際結果一致。
數學推導：為什么差集是正確的？
用數學符號形式化定義：
- 設
f(k)為「不同整數個數 ≤k 的子數組數目」。 - 設
g(k)為「不同整數個數恰好等于k 的子數組數目」。
根據定義，f(k) 是所有 g(1), g(2), ..., g(k) 的和，即：
[ f(k) = g(1) + g(2) + … + g(k) ]
同理，f(k-1) 是：
[ f(k-1) = g(1) + g(2) + … + g(k-1) ]
兩式相減得：
[ f(k) - f(k-1) = g(k) ]
這正是題目要求的「恰好有k種不同整數的子數組數目」。
總結
通過具體例子和數學推導可以看出：
「不超過k的子數組數」減去「不超過k-1的子數組數」，本質是通過「前綴和相減」的方式，精準提取出「恰好等于k」的子數組數目。這種方法將復雜的「恰好k」問題轉化為更易計算的「不超過k」問題，是滑動窗口算法中常用的技巧。
代碼
class Solution {public int subarraysWithKDistinct(int[] nums, int k) {return findNumsofMost(nums, k) - findNumsofMost(nums, k - 1); }private static final int maxn = 20001;private static int[] cnts = new int[maxn];private int findNumsofMost(int[] nums, int k) { Arrays.fill(cnts, 1, nums.length + 1, 0);int ans = 0;for (int r = 0, l = 0, collect = 0; r < nums.length; r ++) { if (++cnts[nums[r]] == 1) { collect ++;}while (collect > k) { if (--cnts[nums[l++]] == 0) { collect--;}}ans += r - l + 1;}return ans;}
}
