C++刷题笔记(4)——leetcode209、904

本文主要是介绍C++刷题笔记(4)——leetcode209、904，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1：209.长度最小的子数组

在这里插入图片描述

暴力解法

解题思路：
用两个for循环，外层for循环负责做子序列的起点，内层for循环负责遍历数组，寻找符合条件的子序列
然后外层for循环移动子序列的起点，继续再数组中寻找新的符合条件的子序列，并与之前找到的子序列长度做比较

时间复杂度O(n^2)

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;                                         //给最终的结果赋一个初始值，INT32_MAX=2^31-1int subLength = 0;                                              //子序列的长度for (int i = 0; i < nums.size(); i++) {                         //设置子序列起点为iint sum = 0;                                                //子序列的数值之和，找一轮子序列后对sum值初始化for (int j = i; j < nums.size(); j++) {                     //设置子序列终止位置为jsum += nums[j];                                         //sum += nums[j]相当于 sum= sum + nums[j]if (sum >= target) {                                    //一旦发现子序列和超过了s，更新resultsubLength = j - i + 1;                              //取子序列的长度result = result < subLength ? result : subLength;   //如果结果的值小于新找到的子序列长度，就更新resultbreak;                                              //找符合条件最短的子序列，所以一旦符合条件就break}}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

滑动窗口

滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出要想的结果。

以target=7，数组[2,3,1,2,4,3]为例：
在这里插入图片描述
滑动窗口也可以理解为双指针法的一种

从动图中可以看出，首先是起始位置指针不懂，然后终止指针在数组中滑动，寻找符合条件的子数组，如果当前窗口的值大于s，窗口就要向前移动（也就是该缩小了）；

移动后如果数组不满足条件，则重复上一步操作，直到找到长度最小的子数组。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;int sum = 0;                                    // 滑动窗口数值之和int i = 0;                                      // 滑动窗口起始位置int subLength = 0;                              // 滑动窗口的长度for (int j = 0; j < nums.size(); j++) {         // 滑动窗口终止位置在数组中遍历寻找符合条件的子数组sum += nums[j];// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while (sum >= s) {subLength = (j - i + 1);               // 取子序列的长度result = result < subLength ? result : subLength;    //更新resultsum -= nums[i++];                      // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）  妙！！！}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

题目2：904.水果成篮

在这里插入图片描述
奇怪的题目，难度一下子上来了，读不懂题的话多看看示例，可以理解为求只包含两种元素的最长连续子序列

滑动窗口

解题思路：
题目的标目就很像滑动窗口，找到符合条件的最大窗口
在这里插入图片描述
用滑动窗口遍历fruits，当有新种类的水果进入窗口时：
1.如果窗口中只有一种水果，将这种水果加入arr数组
2.如果有两种水果，更新窗口的左边界，更新arr中水果的种类
3.如果进来了一种新的类型的水果更新前一种水果的位置
4.更新滑动窗口的最大值


class Solution
{
public:int totalFruit(vector<int>& fruits){int n = fruits.size();unordered_map<int, int> mp;          //unordered_map定义篮子数组，第一个int为数组中的数字、第二个int为数字的个数int ans = 0;                         //滑动窗口大小for (int i = 0, j = 0; j < n; j++)   //用i和j维护滑动窗口 {mp[fruits[j]]++;                 //向篮子中添加种类为j的水果while (mp.size() > 2)            //水果种类大于两种{mp[fruits[i]]--;             //删除先放入篮子中的水果if (mp[fruits[i]] == 0) {    //种类为i的水果数量为0时，删除掉此种类水果mp.erase(fruits[i]);     }i++;                         //更新左边界，更新篮子中水果的种类}ans = max(ans, j - i + 1);       //更新滑动窗口最大值}return ans;}
};