力扣算法面试150题——滑动窗口——个人复习用

第一题209. 长度最小的子数组https://leetcode.cn/problems/minimum-size-subarray-sum/题目内容给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回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 1091 nums.length 1051 nums[i] 104进阶如果你已经实现O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。思路个人感觉滑动窗口有点类似于双指针都是左一根右一根来确定边界只不过双指针中的内容需要是有序的例如非递减而滑动窗口中的顺序是混乱的。本题要找到一个子数组满足总和 target,且长度最小。那就可以例如滑动窗口的思想先右侧边界不断夸张当总和大于target的时候再缩小左侧边界以此类推重复至数组最后一个数。并记录所有满足条件的子数组的长度输出最小值。代码一开始想到用SUM的形式暴力求解结果发现超出了时间限制。这是因为SUM将每次的子区间都计算了一边时间复杂度超了因此不能这么简单的用SUM来算。失败——超时代码时间复杂度O(n2)class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) i 0 # 左侧边界 j 1 # 右侧边界 minsum n 1 while j n : # 使用sum来存储超时 if sum(nums[i:j]) target: i 1 minsum min(minsum, j-i1) else: j 1 # 判定条件若大于列表长度则表示不存在返回0 if minsum n 1: return 0 else: return minsum又注意到每次滑动窗口的变化其实只变一个数要么右移1要么左移1因此不需要这么麻烦每次都对整个滑动窗口内的数值求和一遍只需要用一个额外的变量来存储滑动窗口内的总和然后每次做加或减即可。这样每次更新总和操作的时间复制度就是O(1)class Solution: def minSubArrayLen(self, target: int, nums: List[int]) - int: n len(nums) i 0 j 0 minsum n 1 # 用一个变量来存储代替每次求sum current_sum 0 while j n - 1: current_sum nums[j] # 对左边界进行处理注意用while一开始用了if发现不对 while current_sum target: minsum min(minsum, j-i1) current_sum-nums[i] i 1 # 不管对不对左边界进行收缩右边界始终在动 j 1 return 0 if minsum n 1 else minsum进阶这道题使用滑动窗口之所以能行核心依赖于题目中的这个条件数组里都是正整数。正因为全是正数扩大窗口j1后总和一定变大而缩小窗口i1总和一定变小。这种单调性让滑动窗口极其有效。因此要达到 O(nlogn)我们通常需要用到前缀和二分查找因此代码需要重写。进阶思路遍历前缀和数组prefix_sums的每一个位置j作为子数组的右边界。计算目标值target_val prefix_sums[j] - target。我们需要在prefix_sums[0...j-1]中找到一个最大的下标i使得prefix_sums[i] target_val。或者更直观的思路是在prefix_sums[0...j-1]中二分查找第一个满足prefix_sums[i] prefix_sums[j] - target的下标i。如果找到了这个i说明nums[i...j-1]这个子数组的和 target。此时长度为j - i我们更新最小长度。第二题3. 无重复字符的最长子串https://leetcode.cn/problems/longest-substring-without-repeating-characters/题目内容给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1: 输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。注意 bca 和 cab 也是正确答案。 示例 2: 输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。 示例 3: 输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示0 s.length 5 * 104s由英文字母、数字、符号和空格组成思路整体思路不变。还是先设置滑动窗口的左右边界。然后右边界持续右移中间若是遇到重复的单词就让左边界持续右移还是注意要用while而不是if以及“maxsun max(maxsun, j - i) ”这一行要加在外面第一次尝试踩到的坑。代码class Solution: def lengthOfLongestSubstring(self, s: str) - int: n len(s) # 特殊情况处理有遇到s ,即n 1的时候直接返回1 if n 1: return 1 #滑动窗口的左右边界 i 0 j 1 maxsun 0 while j n: # 若存在重复的字母则左边界持续右移直至不存在重复为止 while s[j] in s[i:j]: i 1 # 右边界不管怎么样都需要右移 j 1 # 最后记录不重复的子串的最大值 maxsun max(maxsun, j - i) return maxsun进阶除了上述方法之外作者复盘时想到可以利用字典getPos的方法记录每一个字母出现的位置这样当需要更新左侧边界的时候只需要读取字典中重复字母的位置就可以快速定位新的左边界不用再向while循环一样每次都11直到不重复为止。是一步定位的使用enumerate获取每个字母以及出现的位置例如{a: 0, b: 1, c: 2}代表“abc”假设此时左边界为0右边界正常向右移动此时为2。下一个字母也是“a”那么就更新左边界将左边界变成 getPos[char]1因此左边界从0变成了1滑动窗口边界变成了[1, 3]对应“bca”然后依旧是在每一步后面计算ans最大值。这样需要注意更新左边界的时候需要加一个max考虑目的是防止左边界左移。因为这种方式相当于直接查表而不是一遍遍while循环因此可以稍微快一点。class Solution: def lengthOfLongestSubstring(self, s: str) - int: # 特殊处理可以加速很多 n len(s) if n 1: return 1 i 0 # 用一个字典统计字母出现的位置用于更新左边界 getPos {} ans 0 # keychar是字母valueright是最近一次出现的位置 for right, char in enumerate(s): # 更新左边界不使用while循环而是直接一步跳转到重复的字母的位置 if char in getPos: i max(i, getPos[char] 1) # 正常往右移动 getPos[char] right ans max(ans, right - i 1) return ans第三题76. 最小覆盖子串https://leetcode.cn/problems/minimum-window-substring/【困难】难度较前两题确实稍微有点难度题目内容给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例 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.lengthn t.length1 m, n 105s和t由英文字母组成进阶你能设计一个在O(m n)时间内解决此问题的算法吗思路核心思路还是利用滑动窗口。先正常右边界向右扩张直到满足条件当前窗口内包含了所有的目标字符再收缩左边界并记录当前最短的窗口情况。一直扩张到最后一个字符为止。这边的难点在于怎么判断当前窗口内容是否包含了所有的目标字符。不可能每次都for循环当前的窗口。因此选择利用defaultfdict的方式先构建一个t的频次统计字典。并构建一个need变量来判断当前是否已经达到条件。具体来说就是在右边界右移的时候会对每一个字符出现的频次-1表示被包含进窗口里了如果该字符不存在t内则会直接变成负数但是对本题不影响这个时候如果是目标字符则need就减一当need等于0的时候开始记录当前窗口信息左、右边界然后开始缩小窗口即左边界右移且要记得处理defaultfict。代码class Solution: def minWindow(self, s: str, t: str) - str: from collections import defaultdict left 0 lookup defaultdict(int) # 先将t中的字符全部放进字典中统计频次 for c in t: lookup[c] 1 # 滑动窗口的左右边界 start, end 0, 0 minlen float(inf) # 设置一个非常大的值默认无穷大后续被更小值替换 # 记录需要进入滑动窗口的有效字符的数量例如“ABC”就是3个 need len(t) res # 右边界开始扩张 while end len(s): # 因为有defaultdict所以不用担心key的问题每遇到一个s中的字符它的值减一小于0也没关系本题不影响 # 如果遇到了目标字符那么need就减一 if lookup[s[end]] 0: need - 1 lookup[s[end]] - 1 # 继续扩张右边界 end 1 # 当need 0的时候说明此时的窗口里已经包含了t中所有字符此时需要记录长度并缩小左边界 while need 0: # 记录更小的值 if end - start minlen: minlen end - start res s[start:end] # 一直缩小左边界直到遇到第一个目标字符该字符会从窗口出去。于是need就要加一 if lookup[s[start]] 0: need 1 # 由于左边界右移lookup中的字符离开窗口了对应的值要加一 lookup[s[start]] 1 start 1 return res