滑动窗口

最小窗口：

1
2
3
4
5
6
7
//i, j分别为窗口的左右指针
while (j < 最大长度) {
    while (满足条件) 
        窗口左边界右移
    更新result
    j ++;
}

lc.76 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    string minWindow(string s, string t) {
        string res = ""; // 初始化
        int len = s.size(); // 最小字串的长度, 初始化为最大
        // i,j为左右指针,diff为s[i...j]和t之间差别个数
        int i = 0, j = 0, diff = t.size(); 
        // map存放t种每个元素及其对应的个数
        unordered_map<char, int> map; 
        for (auto item : t) map[item] ++;

        while (j < s.size()) {
            if (map.count(s[j])) {
                // 差别-1
                if (map[s[j]] > 0) diff --;
                map[s[j]] --; 
            }
            // 当差别diff为0为表示当前窗口中包含t中所有字符
            if (diff == 0) {
                // 当左边界的元素可以不在该窗口中，左边界右移
                while (i < j && (!map.count(s[i]) || map[s[i]] < 0)) {
                    if (map.count(s[i])) map[s[i]] ++;
                    i ++;
                }
                // 当前窗口大小更小时，更新res
                res = len < j - i + 1? res : s.substr(i, j - i + 1);
                len = res.size();
                // 左边界右移一位, 并更新
                map[s[i ++]] ++;
                diff ++; 
            }
            j ++;
        }
        return res;
    }
};

最大窗口

1
2
3
4
5
6
7
//i, j分别为窗口的左右指针
while (j < 最大长度) {
    while (不满足条件) 
        窗口左边界右移
    更新result
    j ++;
}

lc.904 水果成篮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int res = 1;
        // i, j 分别为窗口的左右边界
        int i = 0, j = 1;
        // fir表示窗口内不同于最近一次采摘的另外一种采摘种类
        int fir = fruits[0];
        // map存放窗口内每种水果的<种类, 可直接跳到的位置>
        unordered_map<int, int> map;
        map[fir] = 0;
        while (j < fruits.size()) {
            // 窗口内出现第三种水果
            if (!map.count(fruits[j])) {
                map[fruits[j]] = j;
                if (map.size() > 2) {  
                    map.erase(fir);
                    fir = fruits[j - 1];
                    i = map[fir];
                }
            } 
            // 右边界水果与前一个位置不相同，更新‘可直接跳到的位置’及fir
            else if (fruits[j] != fruits[j - 1]) {
                map[fruits[j]] = j;
                fir = fruits[j - 1];
            }
            // 更新结果
            res = max(res, j - i + 1);
            j ++;
        }
        return res;
    }
};