代码随想录数组二刷：长度最小的子数组（滑动窗口）

leetcode209

这道题采用滑动窗口的思想去做。
实现滑动窗口，主要确定如下三点：

1. 窗口内是什么？
2. 如何移动窗口的起始位置？
3. 如何移动窗口的结束位置？
   窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
   具体代码如下：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = len(nums)
        left,right = 0,0
        min_len = float('inf')
        cur_sum = 0
        while right < l:
            cur_sum += nums[right]
            while cur_sum >= target:
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
            right += 1
        return min_len if min_len!=float('inf') else 0

接下来来具体分析这个代码，因为是滑动窗口，那么这个窗口是怎么构成的呢，是不是就是left和right组成的区间长度，那么何时去计算这个长度，是不是区间里面的和大于等于target时候开始去计算长度。也就是：while cur_sum >= target,然后左边开始移动，移动的原因是因为这个和可能远超你要求的target，所以可以移动左边来缩小窗口。由于你左边移动了，就要把个值从总体的和剔除掉。那么啥时候退出这个内部循环呢。也就是求出的和小于target时候，就去移动右边界。
下面来看水果成篮这道题：

leetcode904

这道题也是采用滑动窗口去解决问题。在做这道题时候，要明白几个问题才能去做好这道题

1. 窗口内是什么？
2. 如何移动窗口的起始位置？
3. 如何移动窗口的结束位置？

这道题窗口内就是能摘的树的数量。但是数组里面的数字相当于是标记一样，这里要用到哈希表去记录一下。因为最多两个篮子，所以种类最多是两种。当超过两个篮子时候，左边窗口开始移动，同时哈希表关于该项的值要减去1，如果该项的值为0，则删除这一项。
具体代码如下：

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        count = collections.defaultdict(int)
        left,max_len,right = 0,0,0
        while right < len(fruits):
            count[fruits[right]] += 1
            while len(count) > 2:
                count[fruits[left]] -= 1
                if count[fruits[left]] == 0:
                    del count[fruits[left]]
                left += 1
            max_len = max(max_len, right - left + 1)
            right += 1
        return max_len

代码步骤解析

1. 初始化变量：

   • count：defaultdict(int)，用于记录窗口内每种水果的数量。
   • left 和 right：窗口的左右边界。
   • max_len：记录遇到的最大窗口长度。

2. 扩展窗口：

   • 使用 right 指针遍历 fruits 数组，每次循环中将 fruits[right] 加入到窗口（即哈希表 count 中增加对应水果的计数）。

3. 调整窗口大小：

   • 当哈希表中的键（即水果类型）数量超过 2 时，开始移动 left 指针缩小窗口，直到窗口内的水果类型数不超过两种。
   • 如果某种水果的数量减到 0，则从哈希表中删除该水果。

4. 更新最大长度：

   • 在每次循环的末尾，更新 max_len 为当前窗口的长度（right - left + 1）和已记录的 max_len 中的较大值。

5. 返回结果：

   • 循环结束后，返回 max_len 作为最大可以摘的水果数量。

性能分析

• 时间复杂度：O(N)，其中 N 是 fruits 数组的长度。尽管内部有一个 while 循环来调整窗口大小，但每个元素最多被加入和删除一次。
• 空间复杂度：O(1)，虽然使用了哈希表，但由于最多只存储两种水果的计数，所以空间复杂度为常数。
  下面继续来看一道题;

leetcode76

这道题也是用滑动窗口+哈希表去做。首先s的长度小于t的长度是一定不满足的，直接返回空字符串即可。
外层while循环依旧控制窗口右边界，内层循环控制左边界。只不过这道题需要用到哈希表记录t对应字符个数。具体代码如下：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""
        hash_t = collections.defaultdict(int)
        hash_s = collections.defaultdict(int)
        min_len = float('inf')
        min_window = ""
        left,right,formed= 0,0,0
        for i in range(len(t)):
            hash_t[t[i]] += 1
        hash_t_lenth = len(hash_t)
        while right < len(s):
            hash_s[s[right]] += 1
            if s[right] in hash_t and hash_s[s[right]] == hash_t[s[right]]:
                formed += 1
            while  formed == hash_t_lenth:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_window = s[left:right+1]
                hash_s[s[left]] -= 1
                if hash_s[s[left]] < hash_t[s[left]]:
                    formed -= 1
                left += 1
            right += 1
        return min_window

下面继续看几道滑动窗口相关的题目：

leetcode3

具体代码如下：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left,right = 0,0
        maxlen = 0
        hashmap = collections.defaultdict(int)
        while right < len(s):
            hashmap[s[right]] += 1
            while hashmap[s[right]] > 1:
                hashmap[s[left]] -= 1
                if hashmap[s[left]] == 0:
                    del hashmap[s[left]]
                left += 1
            maxlen = max(maxlen, right - left + 1)
            right += 1
        return maxlen