Leetcode刷题——滑动窗口

这篇Blog将分享我自己在做Leetcode面试经典150题中滑动窗口部分几道题的思路，let’s go。

209.长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [$nums_l$, $nums_{l+1}$, …, $nums_{r - 1}$, $nums_r$] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 `[4,3]` 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

思路

1. 第一个while循环中total不断累加end位置上的值
2. 第二个循环判断total >= target，这时满足了条件中所说的大于等于
3. 用ans来存储数组，并对其进行最小值比较
4. total和start都后移，窗口滑动一位

提示：

这里的窗口并不是一成不变的，而是不断累加到满足条件，期间窗口可能包含一个两个三个数。

代码

class Solution:
    def minSubArrayLen(self, target:int, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        ans = n + 1
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == n + 1 else ans

时间复杂度

时间复杂度O(n)，执行用时60ms，消耗内存26.9MB

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

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 `"abc"`，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 `"b"`，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 
因为无重复字符的最长子串是 `"wke"`，所以其长度为 3。
请注意，你的答案必须是**子串**的长度，`"pwke"` 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

思路

1. 首先确定需要使用滑动窗口和哈希表
2. 哈希表用于存储字符和其对应的索引
3. 当字符已经存在于哈希表中，对应的滑动窗口左边界移到该字符存储于哈希表中的索引位置
4. 涉及到四个初始变量。n表示s的长度，ans用于存储结果，哈希表mp，指针j表示左边界

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        ans = 0
        mp = {}
        j = 0
        for i in range(n):
            if s[i] in mp:
                j = max(mp[s[i]], j)
            ans = max(ans, i - j + 1)
            mp[s[i]] = i + 1
        return ans

时间复杂度

时间复杂度O(n)，执行用时52ms，消耗内存16.5MB

30.串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：`[0,9]`
解释：
因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：`[]`
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：`[6,9,12]`
解释：
因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

1 <= s.length <= 104

1 <= words.length <= 5000

1 <= words[i].length <= 30

words[i] 和 s 由小写英文字母组成

思路

1. 最开始初始化五个变量，word_len单词长度，total_len单词长度之和，word_map用Counter记录每个单词出现的次数，ans用于存储结果
2. 滑动窗口每次滑动一个单词长度，当我们窗口内的单词出现次数和原本的不匹配就移动右边界，直到窗口内单词计数不超过原始计数

代码

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count
        word_map = Counter(words)
        ans = []

        for i in range(word_len):
            left = i
            right = i
            cur_map = Counter()
            while right + word_len <= len(s):
                word = s[right:right + word_len]
                right += word_len
                if word in word_map:
                    cur_map[word] += 1
                    while cur_map[word] > word_map[word]:
                        cur_map[s[left:left + word_len]] -= 1
                        left += word_len
                    if right - left == total_len:
                        ans.append(left)
                else:
                    cur_map.clear()
                    left = right

        return ans

时间复杂度

时间复杂度O(n * m)，执行时间72ms，消耗内存17.1MB

76 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例1：

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

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

思路

1. 初始化五个变量，need用于记录t每个字符的需求数量，missing用于记录还需要匹配的字符数量，left左边界，start起始位置，min_len长度，ans存储结果
2. 滑动窗口使用right指针遍历字符串s，如果当前字符在need中数量大于0则减少missing表示需求字符少一个
3. 当missing为0即窗口内包含所有所需字符，移动left继续遍历直到 need[s[left]] 不再小于 0。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t: return ""
        need = Counter(t)
        missing = len(t)
        left = start = 0
        min_len = float('inf')
        ans = ""
        
        for right, char in enumerate(s, 1):
            if need[char] > 0:
                missing -= 1
            need[char] -= 1
            
            if missing == 0:
                while left < right and need[s[left]] < 0:
                    need[s[left]] += 1
                    left += 1
                    
                if right - left < min_len:
                    min_len = right - left
                    ans = s[left:right]
                    
                need[s[left]] += 1
                left += 1
                missing += 1
        return ans

时间复杂度

时间复杂度O(n)，执行用时108ms，消耗内存16.8MB

好的，滑动窗口部分的题目就四个，到这里就结束了。滑动窗口的核心思路就在于不断移动窗口去匹配题设所给出的条件，之前刷2024春招100题那会还没特别明白这部分，现在也是彻底会了🤣不过还是不想笔试或面试遇到，这个真的好烦。