904. Fruit Into Baskets
题目就不附了，标准的 sliding window
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> M;
int n = fruits.size(), left = 0;
for (int i = 0; i < n; i++) {
M[fruits[i]] += 1;
if (M.size() > 2) {
M[fruits[left]] -= 1;
if (M[fruits[left]] == 0)
M.erase(fruits[left]);
left += 1;
}
}
return n - left;
}
想讨论的是 sliding window 的形式，通常会看到两种写法
第一种是每次都一定缩到当下的最大合法 window 的，这种比较单纯
第二种是每次最多只缩一格的，像上面写的那样
今天来练习证明看看上面的程式是对的
Claim: 每当程式跑到循环的 i < n 这里时，下面的条件都会成立：
“仅考虑 fruits[0], ..., fruits[i-1] 时的答案会是 i - left”
在最开始 i = 0 时上式显然成立
现在我们用归纳法证明，假设在 i = k 时都成立
我们希望证明经过一次循环后 i 变成 k + 1 时还是成立
在这一次循环 (i = k)，fruits[k] 进来了
根据前提，fruits[0], ..., fruits[k-1] 的答案是 k - left
此时有两种可能
1. fruits[left], ..., fruits[k] 里只有不到两种水果
则目前的答案会是 k-left+1，也就是 fruits[left], ..., fruits[k]
不可能更大，因为 fruits[left-1], ..., fruits[k-1] 一定已经不合法了
否则上一轮的答案会 >= k-left+1，和我们归纳的前提不符
2. fuits[i], ..., fruits[k] 里有超过两种水果
则 fruits[k] 对答案没有帮助，答案还是和上一轮一样，也就是 k-left
在这个 case 时我们的程式会把 left 加一
因此，当程式执行完 i++ 后，i 变成 k + 1
在第一种情形，答案是 k-left+1，所以会等于 i-left
在第二种情形，答案是 k-(上一轮的left)，但因为我们在这种情形会把 left 加一
所以依旧会是 k-(这一轮的left-1) = k+1-left = i-left
因此，程式执行到 i < n 时我们的 Claim 永远正确
最后 i 变成 n 时跳出循环，此时 i-left = n-left 就会是最终答案