2021-1-12 LeetCode 滑动窗口

2021-1-12 LeetCode 滑动窗口

寒假力扣复健第二天

209. 长度最小的子数组

最原始的一题滑动窗口题：
右指针扩大窗口 sum变大，直到符合要求；
左指针先记录此时的窗口大小，然后缩小窗口

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int i=0,j=0;
        int n=nums.size();
        int sum=0;
        int res=n+10;
        // int res=j-i+1;
        while(i=target)
            {
                res=min(res,j-i+1);
                sum-=nums[i];
                i++;

            }

            j++;
        }

        if(res==n+10) return 0;
        else return res;

    }
};

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵
树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

这题稍微改变了一下，目标序列不是target了，而是两种种类；如果大于两种种类就不能记录。

所以是右指针先扩大，先记录res，直到大于两种种类
左指针缩小，直到小于等于两种种类，再记录
（在结果的记录顺序上也是不同的）

用map来模拟数字出现的次数，如果出现新的次数，type++
type>2 收缩窗口
利用哈希表 这是一个通用的方法

class Solution {
public:
    int totalFruit(vector& fruits) {
        int i=0,j=0;
        int n=fruits.size();
        if(n==0) return 0;
        int type=0;
        unordered_map mp;
        int res=0;//res=max(j-i+1,res);

        while(j2&&i<=j)
            {
                if(mp[fruits[i]]>0)
                {
                    mp[fruits[i]]--;
                    if(mp[fruits[i]]==0) type--;
                }
                i++; //放在break前面，因为原来i这个点已经被收缩
                if(type<=2) break;
                

            }
            res=max(j-i+1,res);
            j++;

        }

        return res;
        

    }
};

76. 最小覆盖子串

滑动窗口的思想是一样的，但是其中的细节增加了很多。。。难搞
（wait…）