Sliding Window

slidingwindow

字数统计: 1.4k阅读时长: 7 min

 2021/04/23   Share

滑动窗口

需要注意的主要步骤

移动 right 时扩大窗口，需要更新哪些数据
什么条件下，窗口应该暂停扩大，开始缩小窗口
移动 left 时缩小窗口，需要更新哪些数据
需要的结果是在哪个地方进行更新，是在扩大窗口时，还是缩小窗口时进行更新。

窗口右端不断向前，直到包含所有的所需元素

（注意，刚刚直到包含所有元素就是窗口开始缩小的条件）。

然后窗口左端开始向前（即进行了窗口的缩小），直到开始不包含所有元素（比如ABC，就少了 A，窗口中只包含了BC）
然后窗口右边再次向右前进，重复上述过程。
最后返回最小的窗口即可（在这里，可以得出，在缩小窗口之前通常需要进行预备份上一次的最合适的窗口）

int left = 0, right = 0;
// t  为所需要的匹配元素
while(right < t.size()){
  windows.add[s[right]];
  right++;

  //满足缩减条件时，开始缩减
  while(windows need shrink){
    windows.remove[s[left]];
    left++;
  }

}

76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string “”.

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Example 2:

Input: s = “a”, t = “a”
Output: “a”

Constraints:

1 <= s.length, t.length <= 105
s and t consist of English letters.

Follow up: Could you find an algorithm that runs in O(n) time?

string minWindow(string s, string t) {
  unordered_map<char, int> needs, windows;
  for( char c:t ) needs[c]++;

  int left, right = 0;
  int start = 0;
  int valid = 0;
  int len = INT_MAX;

  //右边界向前滑动的条件
  while(right < s.size()){
    char c = s[right];
    right++;
    if(needs.count(c)){
      windows[c]++;
      if(windows[c] == needs[c]){
        valid++;
      }
    }

    //左边界向前滑动的条件
    while(valid == needs.size()){
      if(right - left  < len){
        start = left;
        len = right - left;
      }
      char d = s[left];
      left++;
      if(needs.count(d)){
        if(windows[d] == needs[d]){
          valid--;
        }
        windows[d]--;
      }
    }
  }
  return len == INT_MAX ? "" : s.substr(start, len);
}

max(O(n)) = O(s+t)

567. Permutation in String

Given two strings s1 and s2, return true if s2 contains the permutation of s1.

In other words, one of s1‘s permutations is the substring of s2.

Example 1:

1
2
3

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1 2	Input: s1 = "ab", s2 = "eidboaoo" Output: false

Constraints:

1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> need, window;
        for (char c : s1 ) need[c]++;

        int left = 0, right = 0;
        int valid = 0;
        while(right < s2.size()){
            char c = s2[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(need[c] == window[c]){
                    valid++;
                }
            }
            // 当 窗口 大于 s1 目标字符串的大小时，需要左移动
            while(right - left >= s1.size()){
                if(valid == need.size() ) return true;
                char d = s2[left];
                left++;
                if(need.count(d)){
                    if(need[d]==window[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return false;
    }

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        unordered_map<char, int> need, window;
        for(char c : p) need[c]++;
        cout<< "first, need.size() = "<<need.size()<<endl;
        int 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()){
                cout<<"need.size() = " << need.size()<<endl;
                cout<<"p.size() = " << p.size()<<endl;
                if(valid == need.size()){
                    res.push_back(left);
                }
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(need[d] == window[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }
};
int main() {
    Solution slt;
    string s1 = "baa", s2 = "aa";
    vector<int> test;
    test = slt.findAnagrams(s1, s2);
    for(int i = 0; i < test.size(); i++){
        cout<< test[i]<< " ";
    }

    return 0;
}

make clear valid == need.size() not valid == p.size().

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

1
2
3

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

1 2	Input: s = "" Output: 0

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0;
        int res = 0;
        unordered_map<char, int> window;
        while(right < s.size() ){
            char c = s[right];
            right++;
            window[c]++;
            while(window[c] > 1){
                char d = s[left];
                left++;
                window[d]--;
            }
          //当缩小窗口时，也就是没有重复子串的时候，此时进行记录最大子串长度。
            res = max(res, right - left);
        }
        return res;
    }
};

int main() {
    Solution s;
    string str = "abcabcbb";
    cout<<s.lengthOfLongestSubstring(str)<<endl;

    return 0;
}

Next Post

CUDA coding
Previous Post

Binary Search

CATALOG

1. 滑动窗口
2. 76. Minimum Window Substring
3. 567. Permutation in String
4. 438. Find All Anagrams in a String
5. 3. Longest Substring Without Repeating Characters

