第零章：我写了首诗，把滑动窗口算法变成了默写题
labuladong
LeetCode
发布日期:   2020-07-25
作者:   M
文章字数:   3.2k
阅读时长:   15 分
热度:  

labuladong 我写了首诗，把滑动窗口算法变成了默写题

  1. 增大窗口
  2. 找到可行解后缩小窗口
  3. 注意维护valid及window中的内容（若包含需要找的元素，才更新window）

滑动窗口算法的思路是这样：

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

76.最小覆盖子串

  1. 遍历t，得到need字典
  2. 窗口左闭右开。先增大右窗口，更新window 和valid （只有need中存在的键，window才会存放）
  3. 找全以后，开始缩小左窗口，相应地，也要更新window和valid。
  4. 在更新左窗口前，先用ans记录并更新左右指针位置来不断缩小子串（非常必要），然后再更新window和valid。这样的话，当窗口的字符串因左窗口的缩小而不再符合要求时（退出while循环），ans中保存的是仍然正好符合要求的左右指针
  5. 如果左指针从未更新过（仍为-1），说明没有在s中找到符合要求的字符串，返回””,否则返回左右指针对应的字符串
  6. ans中，先指到s左右的外面。在更新窗口的过程中，不断缩小ans的范围
  • 在更新窗口过程中
    在增大右窗口时，先window[c]+=1, 然后if window[c]==need[c] 判断；在减小左窗口时，先if window[c]==need[c] 判断，然后window[c]+=1。这是因为 window[c]中的内容要严格与need[c]进行比较，在增大右窗口时，加进window中才能通过if更新valid；在减小左窗口时，通过if更新完valid后才能把当前的windows[c]的计数减1。即：window[c]的更新不能破坏 if ... valid的条件
class Solution:
    def minWindow(self, s,t):
        from collections import defaultdict
        window=defaultdict(int)
        need=defaultdict(int)
        for c in t:
            need[c]+=1
        l,r=0,0
        ans=[-1,len(s)]
        valid=0 # 合法元素的个数
        while r<len(s):
            c=s[r]
            # 增大窗口 ：相应的要改变window和valid
            r+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            # 找到可行解后要缩小窗口：相应的要改变window和valid
            while valid==len(need):
                # 这里先记录当前的子串，非常必要, 确保ans中保存的始终是最短的记录
                if r-l<ans[1]-ans[0]:
                    ans=[l,r]
                c=s[l]
                l+=1
                if c in need:
                    if window[c]==need[c]:
                        valid-=1
                    window[c]-=1
        return "" if ans[0]==-1 else s[ans[0]:ans[1]]
  • 判断键值是否存在于need中时，可以用：if (need.count(c)) 或者if(need.find(c)!=need.end())
//#include <string>
//#include <vector>
//#include <iostream>
//#include <unordered_map>
//using namespace std;

class Solution {
public:
    unordered_map<char, int> need, window;

    string helper(string &s, string &t, vector<int> ans) {
        for (char c:t) {
            need[c] += 1;
        }
        int l = 0, r = 0;
        int valid = 0;
        while (r < s.size()) {
            char c = s[r];
            r += 1;

            // if(need.find(c)!=need.end()){
            if (need.count(c)) {
                window[c] += 1;
                if (window[c] == need[c]) { valid += 1; }
            }

            while (valid == need.size()) {
                if ((r - l) < (ans[1] - ans[0])) {
                    ans[0] = l;
                    ans[1] = r;
                }
                char c = s[l];
                l += 1;
                if (need.count(c)) {
                    if (window[c] == need[c]) { valid -= 1; }
                    window[c] -= 1;

                }
            }


        }
        return (ans[0] == -1) ? "" : s.substr(ans[0], ans[1] - ans[0]);
    }

    string minWindow(string s, string t) {

        vector<int> ans{-1, int(s.size())};
        string res = helper(s, t, ans);
        return res;
    }
};

//int main(){
//    Solution so;
//    string s="ADOBECODEBANC";
//    string t = "ABC";
//    cout<<so.minWindow(s,t)<<endl;
//}

567. 字符串的排列

更新方式1：和上一题类似，找到合法的窗口后，若窗口大小和s1的大小相同，则返回true，否则返回false

  • python写法，注意： 需要有if len(s1) > len(s2): return False,防止corner case的产生
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) > len(s2):
            return False
        l,r,valid=0,0,0
        ans=[-1,len(s2)]
        from collections import defaultdict
        need=defaultdict(int)
        window=defaultdict(int)
        for i in s1:
            need[i]+=1
        while r!=len(s2):
            c=s2[r]
            r+=1
            # 更新右窗口相关的信息
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            # 更新左窗口相关的信息
            while valid==len(need):
                if (ans[1]-ans[0])>(r-l):
                    ans=[l,r]
                d=s2[l]
                l+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        # print(s2[ans[0]:ans[1]])
        return True if (ans[1]-ans[0])==len(s1)  else False 

# so=Solution()
# s1="ab"
# s2 = "a"
# print(so.checkInclusion(s1,s2))

其他写法（与上面写法一致，只是更新细节）

  • 注意，在python中，return时，要确保ans[0]!=-1。
    • 否则有一些corner case会正好满足(ans[1]-ans[0])==len(s1)，导致返回错误的结果（如s1=”ab”, s2=”a”, 此时，ans保存的索引为[-1,1]。 1-（-1）正好为s1的长度，导致错误）
    • 或者把 ans=[-1,len(s2)] 改为ans=[-1,len(s2)+100]，避免这种corner case
  • 整型的最大值可以写为
    import sys 
MAX_INT=sys.maxsize
    所以ans初始化时，可写为ans=[-1,MAX_INT]
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        l,r,valid=0,0,0
        ans=[-1,len(s2)]
        from collections import defaultdict
        need=defaultdict(int)
        window=defaultdict(int)
        for i in s1:
            need[i]+=1
        while r!=len(s2):
            c=s2[r]
            r+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            while valid==len(need):
                if (ans[1]-ans[0])>(r-l):
                    ans=[l,r]
                d=s2[l]
                l+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        # print(s2[ans[0]:ans[1]])
        return True if (ans[1]-ans[0])==len(s1) and ans[0]!=-1 else False 

# so=Solution()
# s1="ab"
# s2 = "a"
# print(so.checkInclusion(s1,s2))

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char,int>need,window;
        for (char c:s1){
            need[c]++;
        }
        int l=0,r=0,valid=0,start=-1,len=INT_MAX;
        while(r<s2.size()){
//            更新右窗口信息
            char c=s2[r];
            r++;
            if (need.count(c)){
                window[c]++;
                if (window[c]==need[c]){
                    valid++;
                }
            }
//            找到了包含s1的窗口（窗口可能比较大，需要缩小左窗口）
            while (valid==need.size()){
                if (r-l<len){
                    start=l;
                    len=r-l;
                }
                char c=s2[l];
                l++;
                if (need.count(c)){
                    if (window[c]==need[c]){
                        valid--;
                    }
                    window[c]--;
                }
            }
        }
        return len==s1.size()? true : false;
    }
};

更新方式2：若窗口大小等于s1长度，则判断窗口的内容是否符合条件。若符合，返回True。否则，继续更新左右窗口

class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        # 准备初始值及统计信息
        from collections import defaultdict
        need=defaultdict(int)
        window=defaultdict(int)
        valid=0
        for c in s1:
            need[c]+=1
        l,r=0,0

        # 维护valid及window
        while r<len(s2):
            # 维护及增大右窗口
            c=s2[r]
            r+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            # 如果窗口大小等于s1长度，则判断窗口的内容是否符合条件
            # 注意是左闭右开，所以是r-l==len(s1)，而不是r-l+1==len(s1)
            if r-l==len(s1):
                # 若符合，返回True
                if valid==len(need):
                    return True

                # 收缩并更新左窗口
                c=s2[l]
                l+=1
                if c in need:
                    if window[c]==need[c]:
                        valid-=1
                    window[c]-=1
        return False

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

更新方式1：相当于在上题_更新方式1_的基础上，找到合法的窗口后，若窗口大小和p的大小相同，则把start加到结果中。因为这时len已缩小，但要从后面继续找符合的子串，所以把len恢复到INT_MAX最大

//#include <string>
//#include <vector>
//#include <iostream>
//#include <unordered_map>
//
//using namespace std;
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        vector<int> res;
        for (char c:p) {
            need[c]++;
        }
        int l = 0, r = 0, valid = 0, start = -1, len = INT_MAX;
        while (r < s.size()) {
//            更新右窗口信息
            char c = s[r];
            r++;
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }
//            找到了包含s1的窗口（窗口可能比较大，需要缩小左窗口）
            while (valid == need.size()) {
                if (r - l < len) {
                    start = l;
                    len = r - l;
                }
//                添加如下代码：当长度相同时，记录当前start，并把len更新到最大
                if (len == p.size()) { // 长度相同，说明在s中找到了一个异位词
//                        cout << "start:" << start << endl;
                    res.push_back(start); // 保存结果
                    len = INT_MAX; // 此时len已经缩小了。因为要从后面继续找符合的子串，所以把len恢复到最大
                }

                char c = s[l];
                l++;
                if (need.count(c)) {
                    if (window[c] == need[c]) {
                        valid--;
                    }
                    window[c]--;
                }
            }
        }
        return res;
    }
};
//int main() {
//    Solution so;
//    string s = "cbaebabacd";
//    string p = "abc";
//    so.findAnagrams(s, p);
//}
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        l,r,valid=0,0,0
        ans=[-1,len(s)+100]
        res=[]
        from collections import defaultdict
        need=defaultdict(int)
        window=defaultdict(int)
        for i in p:
            need[i]+=1
        while r!=len(s):
            c=s[r]
            r+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            while valid==len(need):
                if (ans[1]-ans[0])>(r-l):
                    ans=[l,r]

                # 添加如下代码，如果长度相等，则保存左指针
                if r-l==len(p):
                    res.append(l)

                d=s[l]
                l+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        # print(s2[ans[0]:ans[1]])
        return res

更新方式2：相当于在上题_更新方式2_的基础上，返回所有满足条件的排列的初始索引值。 用res保存结果（用res.append(l) 添加左指针的索引）

# 输入:
# s: "cbaebabacd" p: "abc"
# 输出:
# [0, 6]
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        from collections import defaultdict
        need=defaultdict(int)
        window=defaultdict(int)
        l,r,valid=0,0,0
        res=[]
        for c in p:
            need[c]+=1
        while r<len(s):
            c=s[r]
            r+=1
            if c in need:
                window[c]+=1
                if window[c]==need[c]:
                    valid+=1

            if r-l==len(p):
                if valid==len(need):
                    res.append(l)
                c=s[l]
                l+=1
                if c in need:
                    if window[c]==need[c]:
                        valid-=1
                    window[c]-=1
        return res

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

  • 这次连need和valid都不需要，直接更新window即可
  • while window[c]>1时，说明窗口中存在重复元素，不符合条件，就该移动left缩小窗口了,直到子串再一次无重复
class Solution {
public:
    int res=0;
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> window;
        int l=0,r=0;
        while (r<s.size()){
//            更新右窗口
            char c=s[r];
            window[c]++;
            r++;
//            剔除左边的元素，直到子串再一次无重复
            while (window[c]>1){
                char c=s[l];
                window[c]--;
                l++;
            }
            res=max(res,r-l);
        }
        return res;
    }
};
# 输入: "abcabcbb"
# 输出: 3
# 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        from collections import defaultdict
        window=defaultdict(int)
        l,r=0,0
        res_max=0
        while r <len(s):
            # 更新右窗口
            c=s[r]
            r+=1
            window[c]+=1

            # 符合左窗口更新的条件
            # 注意这里要用while，把不符合条件的左窗口内容一直跳过去
            # 如 "pwwkew"，把左侧p移除后，继续移除左侧w
            while window[c]>1:
                d=s[l]
                l+=1
                window[d]-=1
            # 更新答案
            res_max=max(res_max,r-l)
        return res_max

此题也可用动态规划解(不过耗时较长)：

  • dp数组含义：包含第i个元素的所有无重复字符串的长度（即len(visited)）
  • visited 用于保存无重复字符串元素。visited=[s[i]]一定包含当前元素，然后从 i-1 开始，逆序遍历之前的元素，若不在visited里，则添加到visited，否则break跳出。
  • 最后返回dp数组的最大值
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s)==0:
            return 0
        dp=[1 for _ in range(len(s))]

        for i in range(1,len(s)):
            visited=[s[i]]
            for j in range(i-1,-1,-1):
                if s[j] not in visited:
                    visited.append(s[j])
                else:
                    break
            dp[i]=len(visited)
        return max(dp)

1004. 最大连续1的个数 III

  • 窗口左闭右开，先一步一步右移右窗口，不满足条件时，再右移左窗口。然后更新可行解

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动

class Solution(object):
    def longestOnes(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        res=0
        count=0
        l=0
        r=0
        while r<len(nums):
            if nums[r]==0: # 右移右窗口指针
                count+=1
            r+=1
            while count>k: # 不满足条件时，右移左窗口
                if nums[l]==0:
                    count-=1
                l+=1
            res = max(res, r - l ) # 记录窗口大小；更新左窗口后，窗口内0的个数满足条件，是一个可行解，因此更新结果
        return res
赏

   转载规则


《第零章：我写了首诗，把滑动窗口算法变成了默写题》 由 M 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
第零章：团灭 LeetCode 打家劫舍问题 第零章：团灭 LeetCode 打家劫舍问题
labuladong 团灭 LeetCode 打家劫舍问题 图解动态规划的解题四步骤 动态规划：在确定动态转移方程后，可以用（自顶向下的使用备忘录递归的方法） 自底向上使用 dp 数组的方法 198. 打家劫舍 dp数组表示第i个位置处能取
2020-07-26 LeetCode
labuladong
下一篇 
第零章：我写了首诗，让你闭着眼睛也能写对二分搜索 第零章：我写了首诗，让你闭着眼睛也能写对二分搜索
labuladong 我写了首诗，让你闭着眼睛也能写对二分搜索 二分查找的一个技巧是：不要出现 else，而是把所有情况用 elif 列出来，这样可以清楚地展现所有细节 mid=left + (right - left) // 2 可防止
2020-07-25 LeetCode
labuladong BinarySearch
  目录