仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

滑动窗口

发表于 更新于 分类于 ，
本文字数： 5.4k 阅读时长 ≈ 5 分钟

【道德经·第九章】持而盈之，不如其已。揣(chuǎi)而锐之，不可长保。金玉满堂，莫之能守。富贵而骄，自遗（yí）其咎。功成身退，天之道。

算法模板框架

滑动窗口算法的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案。这里总结一套滑动窗口算法的通用模板：

来源：labuladong的算法小抄

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
void SlideWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for(char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while(right < s.size()) {
        // c是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;

        ...

        /*** debug 输出位置 ***/
        printf("window: [%d, %d]\n", left, right);
        /*********************/

        // 判断左侧窗口是否要收缩
        while(window needs shrink) {
            // d是将移出窗口的字符
            char d = s[left];
            left++;
            // 进行窗口数据的一系列更新
            ...
        }
    }
}

leetcode题目

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minSubArrayLen(int target, vector<int>& nums) {
    int l = 0, r = 0, sum = 0, ans = INT_MAX;
    while(r < nums.size()) {
        sum += nums[r];
        r++;

        while(sum >= target) {
            ans = min(ans, r-l);

            sum -= nums[l];
            l++;
        }
    }

    return ans==INT_MAX ? 0 : ans;
}

713. 乘积小于 K 的子数组

给你一个数组nums和一个整数k，返回子数组内所有元素的乘积严格小于k的连续子数组的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    int l = 0, r = 0, p = 1, ans = 0;
    while(r < nums.size()) {
        p = p*nums[r];
        r++;

        while(p >= k) {
            p = p/nums[l];
            l++;

            if(l == r) break;
        }

        ans += (r>l ? r-l : 0);
    }

    return ans;
}

76.最小覆盖子串

给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。

滑动窗口解法如下：

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
string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for(char c : t) need[c]++;

    int left = 0, right = 0, valid = 0, start = 0, minlen = INT_MAX;
    while(right < s.size()) {
        char c = s[right];
        right++;

        if(need.count(c)) {
            window[c]++;
            if(window[c] == need[c]) 
                valid++;
        }

        while(valid >= need.size()) {
            if(right-left < minlen) {
                minlen = right-left;
                start = left;
            }

            char d = s[left];
            left++;
            if(need.count(d)) {
                if(window[d] == need[d]) 
                    valid--;
                window[d]--;
            }
        }
    }
    return minlen==INT_MAX ? "" : s.substr(start, maxlen);
}

159 至多包含两个不同字符的最长子串

给定一个字符串s，找出至多包含两个不同字符的最长子串t。

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
// 滑动窗口
// 时间复杂度：O(n) 空间复杂度：O(n)
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> window;
        int cnt = 0;                // 不同字符个数
        
        int l = 0, r = 0;    // right指向的是窗口外的下一个字符
        int maxLen = 0;
        while(r < s.size()){
            if(window[s[r]] == 0)
                cnt ++;             // 出现新字符
            
            window[s[r]]++;        // 计数+1并右移
            r++;

            while(cnt > 2){         // 当窗口元素大于2，窗口缩小
                window[s[l]]--;       // 计数-1
                l++;
                
                if(window[s[l]] == 0){
                    cnt --;         // 字符计数减为0
                }
            }

            maxLen = max(maxLen, r-l); // 满足条件的窗口长度
        }
        return maxLen;
    }
};

567. 字符串的排列

给你两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。

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
bool checkInclusion(string s1, string s2) {
    unordered_map<char, int> need, window;
    for(char c : s1) need[c]++;

    int left = 0, right = 0, valid = 0;
    while(right < s2.size()) {
        char c = s2[right];
        right++;

        if(need.count(c)) {
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }

        if(right-left >= s1.size()) {
            if(valid == need.size()) 
                return true;
            
            char d = s2[left];
            left++;
            if(need.count(d)) {
                if(window[d] == need[d]) 
                    valid--;
                window[d]--;
            }
        }
    }
    return false;
}

438. 找到字符串中所有字母异位词

给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。

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
vector<int> findAnagrams(string s, string p) {
    unordered_map<char, int> need, window;
    for(char c : p) need[c]++;

    int left = 0, right = 0, valid = 0;
    vector<int> res;
    while(right < s.size()) {
        char c = s[right];
        right++;

        if(need.count(c)) {
            window[c]++;
            if(window[c] == need[c])
                valid++;
        }

        while(right-left >= p.size()) {
            if(valid == need.size())
                res.push_back(left);

            char d = s[left];
            left++;
            if(need.count(d)) {
                if(window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0, res = 0;
    while(right < s.size()) {
        char c = s[right];
        right++;

        window[c]++;

        while(window[c] > 1) {
            char d = s[left];
            left ++;

            if(window.count(d)) 
                window[d]--;
        }

        res = max(res, right-left);
    }

    return res;
}

395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if (k == 1) {
            return n;
        }
        
        if (k > n) {
            return 0;
        }
        
        int res = 0;
        for (int kind = 1; kind <= 26; kind++) {
            res = max(getRes(s, k, kind), res);
        }
        
        return res;
    }
    
    //kind 窗口内最大字符种类数
    int getRes(string s, int k, int kind) {
        int n = s.length();
        
        int res = 0;
        vector<int> cnt(26);
        
        int left = 0, right = 0;
        int sum = 0;  // 当前窗口内字符种类数
        int total = 0;  // 当前窗口内字符重复次数达到k的种类数
        while (right < n) {
            int indexR = s[right] - 'a';
            cnt[indexR]++;
            if (cnt[indexR] == 1) {
                sum++;
            }
            if (cnt[indexR] == k) {
                total++;
            }
            while (sum > kind) {
                int indexL = s[left] - 'a';
                cnt[indexL]--;
                if (cnt[indexL] == 0) {
                    sum--;
                }
                if (cnt[indexL] == k-1) {
                    total--;
                }
                left++;
            }
            if (sum == total) {
                res = max(res, right-left+1);
            }
            right++;
        }

        return res;
    }
};

小结

滑动窗口算法的思路是这样：
1.我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2.我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3.此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4.重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

位我上者，灿烂星空；道德律令，在我心中。