企业官网建设流程全解析

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

对于任何一道题，如果一开始没思路的话都是从暴力解法开始入手，然后再去优化。对于本题，暴力解法就是枚举出所有的子数组然后选取其中满足条件的并且还要是最短的那个。两层for循环，有一个优化的点，边枚举边定义一个sum变量统计和，满足情况就直接返回，j后边的数字都不用考虑，因为数组全是正整数，越加越大，找到一个满足条件之后再后边的肯定都满足，但是长度肯定比当前这个长。

虽然上述暴力解法也稍微优化了一下，但依旧不够，得继续优化，下述的优化就是同向双指针，也叫滑动窗口，一般在区间出现单调性且双指针不回退的情况下用到这个算法，最重要的就是双指针要不回退就可以用这个算法了。本质就是对暴力双层循环的优化算法。

具体滑动窗口的使用就是差不多包含5步骤，初始化双指针，进窗口，判断窗口是否合法，出窗口，更新结果，其中更新结果和出窗口谁前谁后具体问题具体分析。

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { long long l = 0, r = 0; long long n = nums.size(); long long sum = 0; long long ret = 1e7 + 10;//ret设置为本题数据范围的最大值，方便后边取min int flag = 0; while(r < n) { //进窗口 sum += nums[r]; while(sum >= target) { //更新结果+出窗口 flag = 1; ret = min(r - l + 1, ret); sum -= nums[l++]; } ++r; } //如果一个都没有满足的返回ret即返回的是1e7+10，但题目意思是返回0 //所以设置flag来看看是否区间被修改 if(!flag) return 0; return ret; } };

3. 无重复字符的最长子串 - 力扣（LeetCode）

首先想到的肯定是暴力解法，将全部的不重复子区间都枚举出来比出最长的那一个。

暴力解法显而易见就是O(N^2)的时间复杂度，优化的点也很显然，每次l++的时候r有必要回退吗？很显然没必要，l++之前把l位置的元素从我们的容器里删除即可，然后l++得到的新的[l, r]区间就直接用就可以了，没必要r再回退重新计算，所以本题也是拿双指针去优化。最后一个问题就是怎么判断区间里是否出现了重复的元素，很简单，用map记录一下元素出现的次数，次数>1就说明该val重复了。

一旦想到双指针算法，就是去想5个点，初始化，进窗口，判断窗口是否合法，出窗口，更新结果。

class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); int l = 0, r = 0; map<char, int> mp;//<字符，次数> int ret = -1e7 + 10; while(r < n) { //进窗口 ++mp[s[r]]; //判断合法性 while(mp[s[r]] > 1) { //出窗口 --mp[s[l]]; ++l; } ret = max(ret, r - l + 1); ++r; } return ret == -1e7 + 10 ? 0 : ret; } };

1004. 最大连续1的个数 III - 力扣（LeetCode）

根据题目意思，本题可以转化为寻找数组中最长的一段子数组，其中0的个数不超过k个。我们可以用一个变量zero去记录当前区间里0的个数，只要不超过k个就是合法区间。因此暴力解法诞生，通过下图的分析，可以用同向双指针去优化。

class Solution { public: int longestOnes(vector<int>& nums, int k) { int n = nums.size(); int l = 0, r = 0, zero = 0; int ret = -1e7; while(r < n) { //进窗口 if(nums[r] == 0) ++zero; //判断合法 while(zero > k) { if(nums[l] == 0) --zero; ++l; } //更新结果，根据示例一画画图就知道了 ret = max(ret, r - l + 1); ++r; } return ret; } };

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

定义一前以后两个指针分别指向数组的开头和结束，判断开头和结束的两个数字谁的值与x的差值小就将x减去这个数字，这样可以保证x做减法的次数是最少的，但很遗憾，经过代码验证，这种贪心策略是错误的。

其实本题难就难在不知道选择到底是左边还是右边的数去被x减去，正难则反，我们可以从反面去考虑这个问题，本题的意思不就是找到左边一段区间和右边一段区间使得左右区间的和等于x并且这个左右区间必须是符合要求的最短区间，因为它要求返回的是最小操作数。反过来就是在中间找到一段最长的区间使得这个区间的和等于sum-x，sum表示数组里所有元素的和，即找出最长的子数组的长度，使得子数组里所有元素的和等于sum-x，最后将区间总长度减去这个最长区间的长度不就是答案了。

问题转换后首先想到的暴力解就是找出全部满足里头所有元素之和等于sum-x的区间，然后比出最长的那个就可以了。优化不就是可以用同向双指针吗？因为指针不用回退，每找到一个符合条件的区间的时候，l++之前仅需将原区间里的和扣掉nums[l]即为当前新区间的和，就不用让r回退重复计算了。因为[l, r]是刚好>=sum-x的区间，则[l, r - 1]这段区间必定是<sum-x的，那l++之后r不用回退，因为++l之后的[l, r - 1]区间比++之前的[l, r - 1]区间之和还要小就更不可能>sum-x了，因为数组里全是正数就导致有上边的单调性，所以r只能往后走，不用回退。

class Solution { public: int minOperations(vector<int>& nums, int x) { int sum = 0; for(auto e : nums) sum += e; if(sum < x) return -1; sum -= x; int n = nums.size(); int l = 0, r = 0; int len = -1e7;//表示区间长度 int sm = 0; while(r < n) { //进窗口 sm += nums[r]; //判断窗口是否合法 while(sm > sum) sm -= nums[l++]; //更新结果---必须要判断一下sm==sum //不然会产生一种情况就是sm+=nums[r]直接就>sum了，没有==的环节 //上述情况也不是我们想要的 if(sm == sum) len = max(len, r - l + 1); ++r; } return len == -1e7 ? -1 : n - len; } };

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

本题的意思就是在数组里找一段最长的区间，里边仅只能包含两种类型的数字。首先想到暴力解法，枚举出所有的仅包含两种类型数的区间，比比谁最长即可，如何知道这段区间里有几种类型的数字呢？定义一个变量kind，用map去记录每个数字出现的次数，如果数字的次数从0->1则kind++，从1->0则kind--。用同向双指针去优化，r不用回退，因为l++之后仅需将map里数字的次数--并且判断kind是多少即可，不用r回到l的位置继续重新统计。注：如果说本题数据范围过大，超出int范围，则可以不用kind，直接当mp[fruits[l]]--为0的时候，mp.erase(fruits[l])即可。

class Solution { public: int totalFruit(vector<int>& fruits) { int n = fruits.size(); int l = 0, r = 0; map<int, int> mp; int kind = 0, ret = -1e7; while(r < n) { int t1 = fruits[r]; //进窗口 if(mp[t1]++ == 0) { ++kind; } //判断是否合法 while(kind > 2) { int t2 = fruits[l]; //出窗口 if(mp[t2]-- == 1) { --kind; } ++l; } //更新结果 ret = max(ret, r - l + 1); ++r; } return ret; } };

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

异位词就是两个字符串里的单词的种类以及个数一样但顺序不一样的字符串，比如说"abc"和"cba"。

在统计异位词个数之前先想想怎么判断两个字符串是否是异位词？第一种想法就是排序+便利看看每一个位置的字符是否相同，但是时间复杂度过高，nlogn+n。第二种想法是利用哈希表统计出字符串里每一个字符出现的次数然后便利一遍哈希表跟p字符串里去比较，如果每一个字符出现的次数一样就说明是异位词。

暴力解法，假设p字符串长度为m，先将p里的字符次数统计在一个哈希表里，然后以每m长度的字符串为一组去便利，便利的过程中顺便将每一个字符出现的次数全部统计下来，最后便利一下哈希表比对一下两个哈希表里的数据。

class Solution { public: vector<int> findAnagrams(string s, string p) { //题目里说仅包含26个小写字母 int hashp[26] = {0}; for(auto e : p) ++hashp[e - 'a']; vector<int> ret; int l = 0, r = 0; int hashs[26] = {0}; while(r < s.size()) { //进窗口 ++hashs[s[r] - 'a']; ++r; //判断窗口是否合法 while(r - l > p.size()) { //出窗口 --hashs[s[l] - 'a']; ++l; } if(r - l == p.size()) { int flag = 0; //更新结果---便利哈希表一遍 for(int i = 0;i < 26;i++) { if(hashs[i] != hashp[i]) { flag = 1; break; } } if(!flag) { ret.push_back(l); } } } return ret; } };

这里说一下，如果用的unordered_map，那么上述的代码其实没有改变很多，唯一一个就是判断两个哈希表是否相等时，容器内部是重载了!=运算符的，就不用手动便利了。一旦确定是同向双指针一定按照5个步骤来写代码，不然逻辑混乱很容易死循环。