Hot 100 刷题记录

（1）滑动窗口套路

• 定长滑动窗口

总结成三步：入-更新-出。

入：下标为 i 的元素进入窗口，更新相关统计量。如果窗口左端点 i−k+1<0，即 i<k−1，则尚未形成第一个窗口，重复第一步。

更新：更新答案。一般是更新最大值/最小值。

出：下标为 i−k+1 的元素离开窗口，更新相关统计量，为下一个循环做准备。

比如

for(int i = 0; i < s.size(); ++i) {
    if(uset.count(s[i])) cnt ++;	// 入
    res = std::max(res, cnt);		// 更新答案
    if(i < k - 1) continue;
    if(uset.count(s[i - k + 1])) cnt --; // 出
}

• 不定长滑动窗口

1. 越长越合法：

采取在 while 循环外更新答案

for(...) {
	umap[c] ++;	// 入
    while(umap[c] > 1) { // 合法性判断
        umap[s[left]] --; // 出
        left ++; 
    }
    // 更新
    ans = std::max(ans, right - left + 1);
}

2. 越短越合法：

采取在 while 循环内更新答案

for(...) {
	sum += nums[right];	 // 入
    while(sum >= target) { // 合法性判断
        res = min(res, right - left + 1); // 更新
        sum -= nums[left];	// 出
        left ++;	
	}
}

3. 求子数组个数：

暂时还没刷到