Leetcod面试经典150题刷题记录 —— 滑动窗口篇

滑动窗口就像一只蠕动的蚯蚓，头部前进，尾部蓄力，和双指针天生一对。

1. 长度最小的子数组

题目链接：长度最小的子数组 - leetcode
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [$num{s}_l$, $num{s}_{l+1}$, …, $num{s}_{r?1}$, $num{s}_r$] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
题目归纳：
(1)子数组总和 >= target
(2)子数组要连续 [nums_l, nums_(l+1), … , nums_(r-1), nums_r]
(3)长度为r-(l-1)，值要最小
(4)数组的值均为正整数，所以只管考虑相加

解题思路：
(1) 解法： 见代码。

Python3

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # (1)子数组总和 >= target
        # (2)子数组要连续 [nums_l, nums_(l+1), ... , nums_(r-1), nums_r]
        # (3)长度为r-(l-1)，值要最小
        # (4)数组的值均为正整数，所以只管考虑相加

        # sum[i] = sum (nums[0] + ... + nums[i])
        # 那么子数组[nums_l, nums_(l+1), ... , nums_(r-1), nums_r]的和就会等于 sum[r] - sum[l-1]
        # 与 盛最多水容器 一题类似，移动值更小的边界指针
        n = len(nums)
        if(n == 0):
            return 0

        l, r = 0, 0
        ans_len = 1e9
        sums = 0
        while r < n:
            sums += nums[r]
            while sums >= target: # 这里的l+=1移动值得玩味
                ans_len = min(ans_len, r-(l-1))
                sums -= nums[l]
                l += 1
            r += 1

        if ans_len == 1e9: # 说明所有数组元素加起来都小于target
            return 0
        else:
            return ans_len

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

题目链接：无重复字符的最长子串 - leetcode
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
题目归纳：
(1)如果依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的

解题思路：
(1) 解法： 见代码。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hash_set = set()
        n = len(s)

        right, ans = -1, 0
        for i in range(n):
            if i > 0:
                hash_set.remove(s[i-1]) # 移除起始处前一个位置的元素
            while right + 1 < n and s[right+1] not in hash_set: # 下一个元素不重复，循环这个过程
                hash_set.add(s[right+1])
                right += 1 # 真正右移
            ans = max(ans, right-i+1)
        return ans
            

3. 串联所有单词的子串

3.1 (本题前导题) 找到字符串中所有字母异位词

题目链接：找到字符串中所有字母异位词 - leetcode
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
s 和 p 仅包含小写字母

题目归纳：
题意不难理解。第一步，如果给你两个字符串，长度一致，各字符数量一致，这两个字符串即互为异位词。第二步，滑动窗口寻找。建一个和$p$串长度相同的滑动窗口，在$s$中滑动，那么只要这个窗口字符数量与$p$一致，即为异位词。

解题思路：
(1) 解法： 找到字符串中所有字母异位词 - leetcode官方题解

# (1)python原生写法，数组统计词频
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []
        
        ans = []
        s_count = [0]*26
        p_count = [0]*26
        for i in range(p_len):
            p_count[ord(p[i]) - 97] += 1 # ord()返回对应的unicode编码，97是a的ASCII码值
            s_count[ord(s[i]) - 97] += 1 
        
        if (s_count == p_count): # 词频数组相等
            ans.append(0) # 开头位置就是答案之一
        
        for i in range(1,s_len - p_len+1) : # 滑动窗口的起始位置，最多不会超过s_len - p_len
            s_count[ord(s[i-1]) - 97] -= 1  # 滑动窗口向右滑动中
            s_count[ord(s[i+p_len-1]) - 97] += 1 # 滑动窗口向右滑动，下一个要包括的字符词频+1

            if s_count == p_count:
                ans.append(i) 
        
        return ans

# (2)python中的collections写法，Counter()类统计词频
from collections import Counter # leetcode刷题时，最好把引用也写上，避免到时引用类没有自动提示

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)

        if s_len < p_len:
            return []
        
        ans = []
        s_count = Counter() # Counter()类统计词频，十分好用
        p_count = Counter()

        for i in range(p_len):
            p_count[p[i]] += 1
            s_count[s[i]] += 1
        
        if (s_count == p_count): # 词频数组相等
            ans.append(0) # 开头位置就是答案之一
        
        for i in range(1,s_len - p_len+1) : # 滑动窗口的起始位置，最多不会超过s_len - p_len
            s_count[s[i-1]] -= 1
            s_count[s[i+p_len-1]] += 1

            if s_count == p_count:
                ans.append(i) 
        
        return ans

本题

题目链接：串联所有单词的子串 - leetcode
题目描述：
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
题目归纳：
在有了前导题的基础上，乍一看可以用全排列，先将数组中的子串组合情况全部列出来，然后放入字符串s中进行s.find(sub_str)进行查找，但是这种方式的时间复杂度太高，达到了$O(n!)$，$n$是数组长度。

解题思路：
(1) 解法： 串联所有单词的子串 - leetcode官方题解

from collections import Counter # leetcode刷题时，最好把引用也写上，避免到时引用类没有自动提示

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        # 第438题的元素是字母，此题的元素是单词。438题是求异位词，而这里是求异位字符串
        res = []
        m = len(words)
        n = len(words[0]) # 每个单词长度一致
        s_len = len(s)
        window_len = m*n

        for i in range(n):
            if i + window_len > s_len: # i+偏移量若>s_len则越界，这里偏移量为words长度，即窗口长度m*n
                break
            
            # Counter()类用法: 
            # (1)https://blog.csdn.net/weixin_67683316/article/details/127079849 
            # (2)https://docs.python.org/3/library/collections.html#collections.Counter
            # 这道题中，Counter()也可以理解为hash表，只是更便于调用，用dict()实现也是一样的
            differ = Counter() 
            # 一、对s进行切片，每个切片长度为n，这样才是类似于字母异位词的搜寻。
            # 划分方法为，先删去前i个字母，再对剩余字母进行切片长度为n的划分，若划分至末尾字母长度不足n，也删去
            for j in range(m):
                word = s[i + j*n : i + (j+1)*n]
                # 初始化differ时，出现在窗口中的单词，每出现一次，相应的值+1，
                differ[word] += 1

            for w in words: # 这里遍历循环最好不要写成for word in words, 避免与上面产生阅读歧义
                # 出现在words中的单词，每出现一次，相应的值-1
                differ[w] -= 1
                if differ[w] == 0: # 词频不能低于0，必须删除，要么做减法时加限制条件
                    del differ[w]
            
            # [i, i+n, i+2n,...,s_len - window_len]
            for start in range(i, s_len-window_len + 1, n): 
                if start != i:
                    # 窗口右移，右侧加入新词，左侧移出旧词，对differ做相应的更新
                    new_word = s[start + window_len - n : start + window_len]
                    differ[new_word] += 1
                    if differ[new_word] == 0:
                        del differ[new_word]
                    
                    old_word = s[start-n: start]
                    differ[old_word] -= 1
                    if differ[old_word] == 0:
                        del differ[old_word]
                    
                if len(differ) == 0: # 词频完全一致，则为串联子串，可以append此时索引
                    res.append(start)
        return res

4. 最小覆盖子串

题目链接：最小覆盖子串 - leetcode
题目描述：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 'A'、'B' 和 'C'。

题目归纳：
测试用例保证答案唯一。

解题思路：
(1) 解法： 最小覆盖子串 - leetcode官方题解

官方解法

from collections import Counter # leetcode刷题时，最好把引用也写上，避免到时引用类没有自动提示

class Solution:
    def check(self, window_counter: Counter, t_counter: Counter):
    # 如果window中的词频数量>=t，则是符合条件的
        if window_counter >= t_counter:
            return True
        else:
            return False

    def minWindow(self, s: str, t: str) -> str:
        # 查找s中，涵盖t所有字符的最小子串，像《找到字符串中所有字母异位词》的扩展
        # 《找到字符串中所有字母异位词》是目标长度必须相同，且字符频数也必须相同
        # 这道题只需要字符频数相同，长度可以>=，也就是说，这题的滑动窗口，window_len是不固定的
        # 解题思路
        # (1)称包含t的全部字母窗口，为"可行"窗口
        # (2)双指针l与r。窗口包含t串，左指针l右移，窗口不包含t串，右指针r右移。任意时刻，只有一个指针运动。
        # (3)此时要比较ans_len长度，若ans_len比之前更小，那么更新ans_len与ans。ans_len = r-(l-1)
        # (4)用Counter计算字符频率
        # (5)优化版本，官解未实现。精简无关字符串，就是扔掉一些无关子串，如s=XXABXXC, t=ABC，那么可以扔掉开头的两个XX

        s_len = len(s)
        t_len = len(t)
        if s_len < t_len:
            return ""
        

        window_counter = Counter() # 窗口字频词典
        t_counter = Counter() # t字频词典
        # (1)计算t中字符频率
        for ch in t:
            t_counter[ch] += 1

        # (2)双指针
        l, r = 0, 0
        ans_len = 1e9
        ans = ""

        while r < s_len:

            s_r = s[r]
            if r < s_len and t_counter[s_r] > 0: # r指针未越界，且当前字符在t_counter字频词典中
                window_counter[s_r] += 1 # 窗口中该字频+1
            
            while self.check(window_counter,t_counter) and l <= r: # 在s中找到了包含t的字符串
                window_len = r-l+1
                if window_len < ans_len: # 找到了更小的窗口长度
                    ans_len = window_len
                    ans = s[l: l+window_len]

                s_l = s[l]
                if t_counter[s_l] > 0: # 只在window_counter中，减去与t串相关的字符词频。
                    window_counter[s_l] -= 1 # 左指针向右移动
                    if window_counter[s_l] == 0: # 有无这行判断对求解无影响，为了严谨
                        del window_counter[s_l]
                l += 1 # 窗口包含t串，左指针l右移
            
            r += 1 # 窗口不包含t串，右指针r右移

        return ans

优化解法(我写的不太成功，并未加速)

from collections import Counter # leetcode刷题时，最好把引用也写上，避免到时引用类没有自动提示

class Solution:
    def check(self, window_counter: Counter, t_counter: Counter):
    # 如果window中的词频数量>=t，则是符合条件的
        if window_counter >= t_counter:
            return True
        else:
            return False

    def minWindow(self, s: str, t: str) -> str:
        # 查找s中，涵盖t所有字符的最小子串，像《找到字符串中所有字母异位词》的扩展
        # 《找到字符串中所有字母异位词》是目标长度必须相同，且字符频数也必须相同
        # 这道题只需要字符频数相同，长度可以>=，也就是说，这题的滑动窗口，window_len是不固定的
        # 解题思路
        # (1)称包含t的全部字母窗口，为"可行"窗口
        # (2)双指针l与r。窗口包含t串，左指针l右移，窗口不包含t串，右指针r右移。任意时刻，只有一个指针运动。
        # (3)此时要比较ans_len长度，若ans_len比之前更小，那么更新ans_len与ans。ans_len = r-(l-1)
        # (4)用Counter计算字符频率
        # (5)优化版本，官解未实现。精简无关字符串，就是扔掉一些无关子串，如s=XXABXXC, t=ABC，那么可以扔掉开头的两个XX

        s_len = len(s)
        t_len = len(t)
        if s_len < t_len:
            return ""
    
        window_counter = Counter() # 窗口字频词典
        t_counter = Counter() # t字频词典
        # (1)计算t中字符频率
        for ch in t:
            t_counter[ch] += 1

        # ()优化部分，可选。    
        faster_start = 0 # 更快速的起点位置
        faster_end = s_len - 1 # 更快速的终点位置
        # 优化解法，扔掉s中前面与后面未在t中出现的字符串部分
        while faster_start < s_len:
            if t_counter[s[faster_start]] == 0: # s中的该字符未在t中出现,faster_start可以前进
                faster_start += 1
            else:
                break # 找到了第一个出现的位置就跳出，不再前进
        while faster_end > 0:
            if t_counter[s[faster_end]] == 0:
                faster_end -= 1
            else:
                break

        # (2)双指针
        l, r = faster_start, 0
        ans_len = 1e9
        ans = ""

        while r < faster_end+1:

            s_r = s[r]
            if r < s_len and t_counter[s_r] > 0: # r指针未越界，且当前字符在t_counter字频词典中
                window_counter[s_r] += 1 # 窗口中该字频+1
            
            while self.check(window_counter,t_counter) and l <= r: # 在s中找到了包含t的字符串
                window_len = r-l+1
                if window_len < ans_len: # 找到了更小的窗口长度
                    ans_len = window_len
                    ans = s[l: l+window_len]

                s_l = s[l]
                if t_counter[s_l] > 0: # 只在window_counter中，减去与t串相关的字符词频。
                    window_counter[s_l] -= 1 # 左指针向右移动
                    if window_counter[s_l] == 0: # 有无这行判断对求解无影响，为了严谨
                        del window_counter[s_l]
                l += 1 # 窗口包含t串，左指针l右移
                
            r += 1 # 窗口不包含t串，右指针r右移

        return ans