Day03 | 数组有序数组的平方&&长度最小的子数组

##代码随想录 | Day03 | 数组：有序数组的平方&&长度最小的子数组

主要学习内容：

1.双指针对数组进行操作

2.滑动窗口的一些关键点：

窗口前端后移的情况和条件

977.有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）

当然要使用全都平方再sort的方法啦（bushi

解法：双指针

可以按照三个指针来理解

快慢指针定义：

快指针r：指向正数最大值

慢指针s：指向负数绝对值最大值

第三个指针是循环变量i，是新数组的下标

思路：

快指针指向末尾元素，即正数最大值，慢指针指向首元素，即负数绝对值最大的，快指针所指向的和慢指针所指向的作比较，更大的填写到i所指向的位置，选择了那个指针的值，则那个指针进行移动，另外一个则不动

977.有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int s=0,r=nums.size()-1;//慢快指针
        vector<int> res(nums.size());
        for(int i=nums.size()-1;i>=0;i--)
        {
            if(nums[s]*nums[s]>nums[r]*nums[r])//选慢指针
            {
                res[i]=nums[s]*nums[s];
                s++;//后移
            }
            else
            {
                res[i]=nums[r]*nums[r];//选快指针
                r--;//前移
            }
        }
        return res;
    }
};

关键点：

1.新开一个数组

2.快慢指针的移动

209.长度最小的子数组

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

解法一：暴力解法

思路：两层循环，每次符合条件后就更新res

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int res=0x3f3f3f3f;
        for(int i=0;i<nums.size();i++)
        {
            int sum=0;
            for(int j=i;j<nums.size();j++)
            {
                sum+=nums[j];
                if(sum>=target)//满足条件
                {
                    res=min(j-i+1,res);//更新res
                    break;
                }
            }
        }
         return res == 0x3f3f3f3f ? 0 : res;
    }
};

解法二：滑动窗口（双指针）

滑动窗口（双指针）定义：

滑动窗口后端（慢指针）：外层循环因子，指向子序列首个元素

滑动窗口前端（快指针）：指向子序列末尾元素

二者相减再加一即窗口长度

思路：

慢指针快指针都初始化为0，快指针开始遍历，sum为快慢指针之间的数的和，一旦满足条件，则更新res，同时慢指针向前移动，即滑动窗口前端前移，减去原来滑动窗口前端的值

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int res=0x3f3f3f3f;
        int s=0,sum=0;
        for(int f=0;f<nums.size();f++)
        {
            sum+=nums[f];
            //使用while循环是因为即使滑动窗口继续前移也是满足条件的，例如nums[f]==target，那么f到s之间的数字都将不再需要了，只需要f所指向的一个数即可
            //这样可能更好理解：让sum一直减到小于target（用if的话只减去一次不一定会让sum小于target
            while(sum>=target)//满足条件
            {
                res=min(res,f-s+1);
                sum-=nums[s];
                s++;
            }
        }
         return res == 0x3f3f3f3f ? 0 : res;
    }
};

关键点：

1.快慢指针的定义

2.while循环的含义：让sum一直减到小于target（用if的话只减去一次不一定会让sum小于target

3.在滑动窗口这一算法中，满足什么条件前端后移是很重要的

904.水果成篮

904. 水果成篮 - 力扣（LeetCode）

解法：滑动窗口

题意：

注意不要看错了，是fruits[i]的值表示的水果的类型，而不是i表示类型，fruits[i]表示数量。现在你有两个篮子，你如果选择第i棵树开始采摘，那下一棵树必须是你有的两种篮子中的一个，才能够继续采摘。每棵树上有几个水果咱们不知道，但是咱们每次只能摘一个，所以也就无所谓了。

思路：

现在你有两个篮子，你如果选择第i棵树开始采摘，那下一棵树必须是你有的两种篮子中的一个，才能够继续采摘，如果不是两种类型，那么有两个选择，直接输出最大值和继续采摘，显然这时候不一定是最大值，所以我们只能继续采摘，然后把这次的最大值和以前的最大值比较去一个最大值，你还想继续采摘，就必须舍弃掉除了fruits[i]的另外一种水果类型，因为你是从fruits[i]继承过来的，而舍弃的这一行为就是滑动窗口前端后移的情况。

我们使用哈希表来标记篮子中已经放入的水果种类和该种类的数量，由于只能摘一个，所以滑动窗口的长度其实就是我们所需要求出来的这次滑动的可以采摘的最大值。

关键：

1.哈希表标记水果类型以及数量（存储数量的原因见代码区）

2.滑动窗口前端后移的情况：我们需要舍弃一种水果放下一种来得到新的最大值

3.滑动窗口后端后移的条件：目前所持有的水果类型小于2，即哈希表的大小小于2

举例子：

Leetcode刷题 904. 水果成篮 Fruit Into Baskets_哔哩哔哩_bilibili

重点看举例子部分就行

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map <int,int> p;//存储水果类型和数量
        int s=0,res=0;//慢指针和返回的结果
        for(int f=0;f<fruits.size();f++)//快指针循环
        {
            p[fruits[f]]++;//所获取的该类型的水果数量+1
            while(p.size()>2)//在放入fruits[f]后发现篮子种类多了，舍弃一种
            {
                p[fruits[s]]--;//慢指针所指的类型的数量减1
                if(p[fruits[s]]==0)//减到0后舍弃该类型，减到0后说明该窗口内已经没有该类型的水果了
                     p.erase(fruits[s]);
                    //不用担心减的过程中减掉fruits[f]的类型的水果，因为如果减掉了的话，说明被减掉的和当前的f中间有我们要删去的那种类型的水果，删掉的fruits[f]类型的水果也延续不到下标f的地方，减掉也没事
                s++;//慢指针向前移动
            }
            res=max(res,f-s+1);//更新
        } 
        return res;
    }
};