Array_Sliding window | leecode brushing notes

语言：python

---

An introduction to the idea of ​​sliding windows

Sliding window method contains两个指针,一个用于「延伸」existing window的j指针,和一个用于「收缩」窗口的 i 指针.在任意时刻,只有一个指针运动,而另一个保持静止. 我们在 数组 上滑动窗口,通过移动 j 指针不断扩张窗口.当窗口包含 target 全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口.

209. 中等长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target .
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度.如果不存在符合条件的子数组,返回 0 .

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 0
        lenf = len(nums) + 1
        total = 0
        i=0
        j=0
        while(j<len(nums)):
            total += nums[j]
            j += 1
            while (total >= target):
                lenf = min(lenf, j-i)
                total -= nums[i]
                i += 1
        if lenf == len(nums) + 1:
            return 0
        else:
            return lenf

904. 中等水果成篮

题目：你正在探访一家农场,农场从左到右种植了一排果树.这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 .
.
你想要尽可能多地收集水果.然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果：
.
你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果.每个篮子能够装的水果总量没有限制.
你可以选择任意一棵树开始采摘,你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 .采摘的水果应当符合篮子中的水果类型.每采摘一次,你将会向右移动到下一棵树,并继续采摘.
一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘.
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目.

lass Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()  # count = Counter({1: 2, 2: 1}), 统计每个元素：对应元素的个数
      
        for j, x in enumerate(fruits):  # i is index, x is value
            count[x] += 1
            print(f"count = {
      count}")
            while len(count) >= 3:  # len(count) 用于统计元素的个数.When the element type is greater than 3时,执行下述操作
                count[fruits[i]] -= 1
                print(count)
                if count[fruits[i]] == 0:  # 按照顺序,Delete the category with the least number of the three categories
                    del count[fruits[i]]
                i += 1
            ans = max(ans, j-i+1)
            print(f"ans = {
      ans}")
        return ans

python enumerate用法总结
Python collections.Counter()用法
输出结果

count = Counter({
    1: 1})
ans = 1
count = Counter({
    1: 1, 2: 1})
ans = 2
count = Counter({
    1: 2, 2: 1})
ans = 3
count = Counter({
    1: 2, 2: 2})
ans = 4
count = Counter({
    1: 2, 2: 2, 3: 1})
Counter({
    2: 2, 1: 1, 3: 1})
Counter({
    1: 1, 2: 1, 3: 1})
Counter({
    2: 1, 3: 1, 1: 0})
ans = 4
count = Counter({
    3: 2, 2: 1})
ans = 4
count = Counter({
    3: 3, 2: 1})
ans = 4
count = Counter({
    3: 4, 2: 1})
ans = 5
count = Counter({
    3: 5, 2: 1})
ans = 6

76. 困难最小覆盖子串

题目：给你一个字符串 s 、一个字符串 t .返回 s 中涵盖 t 所有字符的最小子串.如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” .
.
注意：
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量.
如果 s 中存在这样的子串,我们保证它是唯一的答案.

待学……