Skip to main content

滑动窗口

番风May 4, 2024About 4 min

209. 长度最小的子数组 - 力扣（LeetCode）

题目描述：有 n 个正整数数组和一个正整数 target， 找出数组中满足其总和大于等于 target 的最小的 子数组（子数组：连续的数组）

  • 方法一：双指针，从右开始滑动， 如果现有的和大于了 target 就将左指针向右滑动。时间复杂度 O(n),左和右最多移动 n 次， 空间复杂度 O(1)
  • 方法二：暴力法，每个下标开始依次求和，大于等于 target 后就更新最小长度。
  • 方法三： 前缀和 + 二分 这里其实就是暴力法的改良，对于求和操作进行改良，因为题目条件说过所有的数都是正整数，所以可以维护一个前缀和数组，在前缀和数组上二分。
    注意：
    这里简单用滑动窗口, 这个窗口是右 for 左 while的.
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_length = 10**6
        sum = 0
        left = 0
        for right in range(len(nums)):
            sum += nums[right]
            while sum >= target:
                min_length = (
                    (right - left + 1)
                    if (right - left + 1) < min_length
                    else min_length
                )
                sum -= nums[left]
                left += 1
        min_length = min_length if min_length != 10**6 else 0
        return min_length

76. 最小覆盖子串 - 力扣（LeetCode）

题目描述：给你两个字符串 S 和 T， 返回 S 中涵盖 T 中所有字符的最小子串。

  • 方法一：滑动窗口，右 for 满足需求后就开始 左while 来更新。满足需求函数写个字典来记录。
  • 方法二：
  • 方法三：
    注意：
    这题主要需要考虑的是 t 中出现重复字符的问题, 我的解决方法是做个字典, 来供删除,
    实际做起来还是比较清晰的, 就是窗口移动时的逻辑需要判断, 个人感觉可以一边写一边 print 不断调试
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        curr = self.constrcut_t(t)
        right = 0
        return_str = ""
        min_length = 10**5
        for i in range(len(s)):
            while not self.is_satisfied(curr) and right < len(s):
                if s[right] in curr:
                    curr[s[right]] -= 1
                right += 1
            if right - i < min_length and self.is_satisfied(curr):
                return_str = s[i:right]
                min_length = right - i
            if s[i] in curr:
                curr[s[i]] += 1
        return return_str
    def is_satisfied(self, curr: dict):
        for key, value in curr.items():
            if value >= 1:
                return False
        return True
    def constrcut_t(self, t):
        cur = {}
        for i in range(len(t)):
            if t[i] in cur:
                cur[t[i]] += 1
            else:
                cur[t[i]] = 1
        return cur

ts 实现,发现 ts 再做的时候比第一遍好看多了

function minWindow(s: string, t: string): string {
  let dir: { [key: string]: number } = {};
  for (let i = 0; i < t.length; i++) {
    if (t[i] in dir) {
      dir[t[i]] += 1;
    } else {
      dir[t[i]] = 1;
    }
  }
  let l = 0;
  let r = 0;
  let min = 10 ** 5;
  let returnString = "";
  for (let r = 0; r < s.length; r++) {
    if (s[r] in dir) {
      dir[s[r]] -= 1;
    }
    while (isSatisfied(dir) && l <= r) {
      if (r - l < min) {
        min = r - l;
        returnString = s.slice(l, r + 1);
      }
      if (s[l] in dir) {
        dir[s[l]] += 1;
      }
      l += 1;
    }
  }
  return returnString;
}
function isSatisfied(dir: { [key: string]: number }): boolean {
  for (let item of Object.values(dir)) {
    if (item > 0) {
      return false;
    }
  }
  return true;
}

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目描述：给定两个字符串 s 和 p，找出 s 中所有 p 的异位词的子串，返回子串的索引。

  • 方法一： 定长滑动窗口。
  • 方法二：
  • 方法三：
    注意：
    这种题目还是要注意构造一个 dist 来记录存在过的字符, 只要考虑到滑动窗口就行了, 不要给自己上难度.
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        right = 0
        curr = self.construct(p)
        return_list = []
        for left in range(len(s) - len(p) + 1):
            while right - left < len(p):
                if s[right] in curr:
                    curr[s[right]] -= 1
                    if self.is_satisfied(curr):
                        return_list.append(left)
                right += 1
            if s[left] in curr:
                curr[s[left]] += 1
        return return_list
    def is_satisfied(self, curr):
        for key, value in curr.items():
            if value != 0:
                return False
        return True
    def construct(self, p):
        dir = {}
        for i in range(len(p)):
            if p[i] in dir:
                dir[p[i]] += 1
            else:
                dir[p[i]] = 1
        return dir

930. 和相同的二元子数组 - 力扣（LeetCode）

题目描述 ： 一个数组全部是由 0 和 1 组成的， 求所有和等于 target 的子数组。

  • 方法一：前缀和 + 哈希表， 做个前缀和的数组，遍历该数组，更新哈希表， 如果数组里有 preSum-goal，就更新 count。
  • 方法二：使用滑动窗口，恰有x个元素的窗口 = 最多含x个元素的窗口- 最多含x-1个元素的窗口
  • 方法三：
    注意：
    拼尽全力也无法战胜, 我真的哭死
    image.png|200
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        sum = 0
        left = 0
        count = 0
        for r in range(len(nums)):
            sum += nums[r]
            while sum > goal and left < r:
                sum -= nums[left]
                left += 1
            temp = left
            if sum == goal:
                temp = left
                while temp <= r:
                    if nums[temp] == 0:
                        count += 1
                    elif nums[temp] == 1:
                        count += 1
                        break
                    temp += 1
        return count

之所以做不出来是因为 temp=left 这里回头了
全新方法:
这个窗口为什么不行, 因为你在强行构造 恰有x个元素的窗口, 实际上
恰有x个元素的窗口 = 最多含x个元素的窗口- 最多含x-1个元素的窗口
而这个 最多元素 的窗口可以不用回头的窗口构建!!!, 这个思维转变非常关键

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def at_most(nums, goal):
            if goal < 0:
                return 0
            res = 0
            count = 0
            left = 0
            for right in range(len(nums)):
                count += nums[right]
                while count > goal:
                    count -= nums[left]
                    left += 1
                res += right - left + 1
            return res
        return at_most(nums, goal) - at_most(nums, goal - 1)

同样的题目

3. 无重复字符的最长子串 - 力扣（LeetCode）

Default footer
Copyright © 2024 番风