【LeetCode 刷题】数组-滑动窗口

此博客为《代码随想录》数组章节的学习笔记，主要内容为滑动窗口知识点的相关题目解析。

文章目录

• 209.长度最小的子数组
• 904. 水果成篮
• 76. 最小覆盖子串

209.长度最小的子数组

题目链接

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = curSum = 0
        ans = float('inf')
        for right in range(len(nums)):
            curSum += nums[right]
            while curSum >= target:  # 尽量缩小子数组长度
                ans = min(ans, right - left + 1)
                curSum -= nums[left]
                left += 1
        return ans if ans != float('inf') else 0      

• 滑动窗口，right 指向终止位置，每次循环都会向后移动一位；left 指向起始位置，动态调整位置。
• 特点：题目提供的是要满足的条件，求最小长度。
  • 在每个循环新的终止位置元素进入窗口后，while 循环尽可能弹出窗口左侧的元素，直到不满足条件。
  • 答案更新放在 while 循环中理解比较直观。（放在循环外也可）

904. 水果成篮

题目链接

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = defaultdict(int)
        left = ans = 0
        for right, in_ in enumerate(fruits):
            cnt[in_] += 1
            while len(cnt) > 2:
                out = fruits[left]
                cnt[out] -= 1
                if cnt[out] == 0:
                    del cnt[out]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

• defaultdict(int) 创建了一个 defaultdict 对象，其中 int 是一个工厂函数，返回 0。
  • 访问已存在的键时，defaultdict 会返回对应的值。
  • 访问不存在的键时，defaultdict 会调用 int() 函数，返回默认值 0。
• 特点：特点：题目提供的是要避免的条件，求最大长度。
  • 在每个循环新的终止位置元素进入窗口后，while 循环尽可能弹出窗口左侧的元素，直到满足条件。
  • 答案更新放在 while 循环外。

76. 最小覆盖子串

题目链接

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left = -1
        minLen = float('inf')
        cnt = defaultdict(int)
        for t_ in t:
            cnt[t_] += 1
        less = len(cnt) # 还差几种字符能够满足覆盖
        
        left = 0
        for right, in_ in enumerate(s):
            cnt[in_] -= 1
            if cnt[in_] == 0:
                # 在 in_ 元素移入窗口之后检查
                # 原来 > 0（差字符），现在 = 0（刚好不差）
                less -= 1
            while less == 0:
                if right - left + 1 < minLen:
                    minLen = right - left + 1
                    ans_left = left
                out_ = s[left]
                if cnt[out_] == 0:
                    # 在 out_ 元素移出窗口之前检查
                    # 现在 = 0（刚好不差），移除后 > 0（差字符）
                    less += 1
                cnt[out_] += 1
                left += 1
        return "" if ans_left == -1 else s[ans_left: ans_left + minLen]

• 优化思路：由于每次移入和移出窗口的都为单个元素，因此在测试是否满足条件时，仅考虑当前变动元素。
• 实现方式：添加 less 变量，用于记录还差几种字符能够满足覆盖（并不是几个）
  • 在字符移入移出时，如果当前字符出现（不差字符）和（差字符）两个状态之间的转换，则更新 less 变量。
  • less == 0 表示所有需要的字符种类均满足，实现覆盖