Bryce's Blog

Learn Everything.

0%

双指针滑动窗口算法总结

发表于 分类于 阅读次数： 149 Valine： 0
本文字数： 4.8k 阅读时长 ≈ 4 分钟

滑动窗口算法，这个算法技巧的思路非常简单，就是利用双指针维护一个窗口，不断滑动，然后更新答案。LeetCode上有差不多10道运用滑动窗口算法的题目，难度都是中等和困难。该算法的大致逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left = 0, right = 0;

while (right < s.size()) 
{
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) 
    {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

这个算法技巧的时间复杂度是 O(N)，比一般的字符串暴力算法要高效。

要注意各种细节问题。比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果等。算法基本框架如下：

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
/* 滑动窗口算法框架 */
void slidingWindow(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 原题为例来套这个框架

1、最小覆盖子串

使用暴力解法，代码大概是这样的：

1
2
3
4
for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案

滑动窗口算法思路：

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 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

下面画图理解一下，needs和window相当于计数器，分别记录T中字符出现次数和「窗口」中的相应字符的出现次数。

初始状态：

增加right，直到窗口[left, right)包含了T中所有字符：

现在开始增加left，缩小窗口[left, right)。

直到窗口中的字符串不再符合要求，left不再继续移动。

之后重复上述过程，先移动right，再移动left…… 直到right指针到达字符串S的末端，算法结束。

首先，初始化window和need两个哈希表，记录窗口中的字符和需要凑齐的字符：

1
2
unordered_map<char, int> need, window;
for (char c : t) need[c]++;

然后，使用left和right变量初始化窗口的两端，不要忘了，区间[left, right)是左闭右开的，所以初始情况下窗口没有包含任何元素：

1
2
3
4
5
int left = 0, right = 0;
int valid = 0; 
while (right < s.size()) {
    // 开始滑动
}

其中valid变量表示窗口中满足need条件的字符个数，如果valid和need.size()的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。

现在开始套模板，只需要思考以下四个问题：

1、当移动right扩大窗口，即加入字符时，应该更新哪些数据？

2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口？

3、当移动left缩小窗口，即移出字符时，应该更新哪些数据？

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加window计数器；如果一个字符将移出窗口的时候，应该减少window计数器；当valid满足need时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

下面是完整代码：

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

    int left = 0, right = 0;
    int valid = 0;
    int n = s.size();
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = n+1;
    while (right < n) 
    {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) 
        {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size())
        {
            // 在这里更新最小覆盖子串
            if (right - left < len)
            {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d))
            {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 返回最小覆盖子串
    return len == n+1 ? "" : s.substr(start, len);
}

2、字符串排列

注意哦，输入的s1是可以包含重复字符的，所以这个题难度不小。

这种题目，是明显的滑动窗口算法，相当给你一个S和一个T，请问你S中是否存在一个子串，包含T中所有字符且不包含其他字符？

首先，先套用滑动窗口算法框架代码，然后明确刚才提出的 4 个问题，写出如下代码：

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
// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size())
        {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d))
            {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

3、找到字符串中所有字母异位词

相当于，输入一个串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
33
34
35
36
vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> needs, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) 
    {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (needs.count(c)) {
            window[c]++;
            if (window[c] == needs[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left == t.size()) 
        {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == needs.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d))
            {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入res即可。

4、最长无重复子串

根据提出的四个问题，依次根据具体情况填入框架即可，

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> m;

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) 
    {
        char c = s[right++];
        // 进行窗口内数据的一系列更新
        m[c]++;
        // 判断左侧窗口是否要收缩
        while (m[c] > 1)
        {
            char d = s[left++];
            // 进行窗口内数据的一系列更新
            m[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}

当m[c]值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动left缩小窗口。

要在收缩窗口完成后更新res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复元素了。

参考

相关文章推荐
喜欢你就打赏一下
来发评论吧~
Powered By Valine
v1.5.2