一、将x减到0的最小操作数

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

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= x <= 10^9

 方法一：暴力枚举法。这道题直接用暴力法还不好做，因为情况太多了，可能能左边一个右边一个，也可能左边多个右边多个，也可能左边没有右边多个，也可能左边多个右边没有。

所以直接上手这道题代码非常不好写，当我们遇到正着想难以解决时，就可以考虑反着来思考。

题目的意思可以转化为：从中间部分找到最长的一片区域使其和等于nums数组中元素所有的和减去x。如果能找到这片区域就返回最长的，如果没有找到这片区域就返回-1。

根据转换后的意思，我们可以上手暴力解法，分析如下(以示例1为例)：

代码实现(C++，时间复杂度O(N^2))：

//方法一：暴力枚举法
class Solution {
public:int minOperations(vector<int>& nums, int x) {int n = nums.size();//数组元素个数int len = -1;//记录子串中满足条件的最大长度int arrSum = 0; //记录数组中所有元素的和for(auto e: nums)arrSum+=e;int target = arrSum - x; //目标值if(target < 0)return -1;if(target == 0) //如果target为0，那么就说明要移除数组的全部元素return n;for(int left = 0; left < n; ++left){int sum = 0;//记录left到right之间的元素的和for(int right=left;right<n;++right){sum+=nums[right];if(sum == target)len = max(len, right-left+1);}}return len == -1 ? -1 : n - len ;}
};

 运行结果：

可见当数据量过多时用暴力解法就会超时。

所以我们要进行优化，我们的优化是在暴力解法的基础上进行的，分析如下：

代码实现(C++，时间复杂度O(N))： 

//方法二：滑动指针
class Solution {
public:int minOperations(vector<int>& nums, int x) {int n =nums.size(),len = -1;int arrSum = 0; //记录数组所有元素的和for(auto e : nums)arrSum += e;int target = arrSum - x;if(target < 0) //特殊情况单独处理return -1;int sum = 0;//记录left到right之间所有元素的和for(int left = 0,right = 0;right < n; ++right) //最终结束条件是right==n{sum+=nums[right]; //入窗口while(sum > target)  //判断sum -= nums[left++]; //出窗口if(sum == target) //满足条件就更新lenlen = max(len,right-left+1);}return len == -1 ? -1 : n-len;}
};

代码中虽然是两层循环，但是结合实例，我们的left指针和right指针都是不回退的，两者最多都往后移动n次，因此时间复杂度是O(N)。相比于暴力解法，这种优化的方法效率更高。  

二、水果成篮

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

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

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

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

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

初看这道题目时，可能不好理解，我以示例4为例解释一下：

这个问题的本质就是：在数组中找出一个最长的子数组的长度，要求子数组中的水果种类不能超过两种。

方法一：暴力枚举法。暴力枚举的过程就如上面解释示例4的过程差不多，在暴力枚举的过程中需要统计水果的种类，用来控制停下的条件，统计水果的种类就需要借助哈希表，遇到一个新品种就加入到哈希表中，如果哈希表中的元素个数大于2，就停止，然后枚举下一种情况，依次进行...。

代码实现(C++，时间复杂度O(N^2))：

//方法一：暴力枚举法
class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int ret = 0; //记录收集水果最大数目 for(int left = 0;left<n;++left){unordered_map<int,int> hash; //统计水果种类，以及该种类出现的个数for(int right=left;right<n;++right){hash[fruits[right]]++;if(hash.size() > 2) //水果种类大于2break;ret = max(ret,right-left+1); //如果水果种类小于2，就更新ret}}return ret;}
};

运行结果：

当数据量过大时，暴力解法就会超时。

所以我们需要对其进行优化，分析如下：

代码实现(C++，时间复杂度O(N))：

//方法二：滑动指针
class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int ,int>hash; //用来记录水果的种类以及对应的水果数int n = fruits.size();//数组中元素个数int ret = 0; //收集水果最大数for(int left=0,right=0;right<n;++right){   //入窗口hash[fruits[right]]++; //判断while(hash.size() > 2){   //出窗口hash[fruits[left]]--; if(hash[fruits[left]] == 0) //表示该种类的水果个数已经为0了，就需要从哈希表中删除该水果hash.erase(fruits[left]);++left; //更新left}//当水果种类小于等于2时更新retret = max(ret,right-left+1);}return ret;}
};

因为对hash进行频繁插入和删除， 这种操作是比较耗时的。所以我们可以稍微优化一下，用数组来模拟哈希表：

//方法二：滑动指针
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001] = {0};//根据题目，最多有10^5个水果，所以直接开一个大一点的数组，包含所有情况int n = fruits.size();//数组中元素个数int ret = 0; //收集水果最大数int kinds = 0;//表示窗口内一种有多少种水果for(int left=0,right=0;right<n;++right){   if(hash[fruits[right]] == 0)++kinds; //维护水果种类//入窗口hash[fruits[right]]++; //判断while(kinds > 2){   //出窗口hash[fruits[left]]--; if(hash[fruits[left]] == 0) --kinds;++left; //更新left}//当水果种类小于等于2时更新retret = max(ret,right-left+1);}return ret;}
};

 三、找到字符串中所有字母异位词

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母

先来解释一下题目的意思(以示例1为例)：

明白题意后，先考虑一个问题，给定两个字符串，如何判断它们两个是异位词？

法一：将这两个字符串按字典序先排序，然后用两个指针，分别指向这两个字符串的起始位置，遍历过程中依次比较，若每个位置都相等，那么它们两个字符串就是异位词。

法二：记录字符串1中的字符以及它出现的次数，再记录字符串2中的字符以及它出现的次数， 可以用哈希表记录字符以及出现的次数。若两个哈希表相等，那么它们两个字符串就是异位词。

法二是更方便的。

据此，我们的暴力解法就来了，先用哈希表1来存储p中每个字符出现的次数，接着记录p中字符串的长度m，在s中暴力找出所有长度为m的子串，用哈希表2来依次存储这些子串，当存储第一个时，就和哈希表1进行比较，若相等，将这个子串在s中的起始位置的下标存放到一个容器中。接着哈希表2再来存储下一个子串，再比较...直到s中所有长度为m的子串比较完。

 代码实现(C++，时间复杂度O(N))：

//方法一：暴力枚举法
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;//存放符合要求的下标int m = p.size(); //记录p的长度if(m > s.size()) //处理特殊情况return ret;int hash1[30]={0};//小写字母个数不会超过30个,用数组模拟哈希表for(auto e : p)hash1[e-'a']++;for(int begin = 0;begin<=s.size()-m;++begin){int hash2[30]={0};string son = s.substr(begin,m);for(auto e : son)hash2[e-'a']++;//比较hash1和hash2是否相等for(int i=0;i<30;++i){if(hash1[i]!=hash2[i])break;if(i==29) //说明hash1等于hash2ret.push_back(begin); //在结果容器插入起始下标}   }return ret;}
};

这种暴力代码虽然能通过，但是将所有子串全部找出依次比较，效率还是太低了，所以我们可以考虑优化一下，分析如下(以示例1为例)：

代码实现(C++，时间复杂度O(N))： 

//方法二：滑动指针
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int m = p.size();int hash1[30]={0};for(auto e:p)hash1[e-'a']++;int hash2[30]={0};for(int left=0,right=0;right<s.size();++right){hash2[s[right]-'a']++; //进窗口if(right-left+1 > m) //判断hash2[s[left++]-'a']--; //出窗口,更新leftif(right-left+1 == m){//判断hash1和hash2是否相等for(int i=0;i<30;++i){if(hash1[i]!=hash2[i])break;if(i==29)ret.push_back(left);}}}return ret;}
};

此时问题已然解决，但我们还可以对更新结果的判断条件进行优化：

利用count来记录窗口内"有效字符"的个数，所谓有效字符就是能和p中字符进行匹配的字符且数量不能超过p中该字符的个数。那么就可以将更新结果的判断条件改为if(count == m){}这种形式。

代码如下：

//方法二：滑动指针
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int m = p.size();int hash1[30]={0};for(auto e:p)hash1[e-'a']++;int hash2[30]={0};int count = 0; //记录窗口中"有效字符的个数"for(int left=0,right=0;right<s.size();++right){hash2[s[right]-'a']++; //进窗口if(hash2[s[right]-'a'] <= hash1[s[right]-'a'])count++;  //说明s[right]这个字符有效if(right-left+1 > m) //判断{if(hash2[s[left]-'a'] <= hash1[s[left]-'a'])count--; //说明s[left]这个字符有效hash2[s[left++]-'a']--; //出窗口,更新left}if(count == m)  ret.push_back(left); }return ret;}
};

四、串联所有单词的子串

30. 串联所有单词的子串 - 力扣（LeetCode）

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

这道题初看感觉无从下手，但是我们可以以一种特别的眼光来看待此题(以示例1为例)：

但它与上道题的有几个不同点：

1、哈希表

上道题中我们是用数组来模拟哈希表的，之所以能这么做是因为在哈希表中存放的是一个个字符。

这道题就不能用数组来模拟哈希表了，因为这道题是以字符串为单位的，所以要用一个容器来存放数据，这里用unordered_map这个容器来记录。

2、left和right指针的移动

这道题中指针每次移动的距离不在是1了，而是单词的长度(len)。

3、滑动窗口的执行次数

上道题中滑动窗口只需执行1次，而这道题中滑动窗口需要执行len次。

代码实现(C++，时间复杂度O(N))：

//方法：滑动窗口
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret; //记录最终结果unordered_map<string,int> hash1; //存储words中所有单词的频次for(auto e:words)hash1[e]++;int len = words[0].size(); //words中每个单词长度相同int m = words.size(); //记录words中单词的个数for(int i=0;i<len;++i) //滑动窗口执行len次{unordered_map<string,int> hash2;//维护窗口内单词的频次int count = 0; //窗口内有效单词的个数//每一次滑动窗口执行过程for(int left=i,right=i;right<(int)s.size()-len+1;right+=len) //注意right的更新,s.size()的返回值是无符号整形，它减len可能小于0，所以要强转一下{//进窗口 + 维护countstring in = s.substr(right,len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in])++count;//判断if(right-left+1 > len*m){//出窗口 + 维护countstring out = s.substr(left,len);if(hash1.count(out) && hash2[out] <= hash1[out])--count;hash2[out]--;left+=len;}//更新结果if(count == m)ret.push_back(left);}}return ret;}
};

五、最小覆盖子串

 76. 最小覆盖子串 - 力扣（LeetCode）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s 和 t 由英文字母组成

 方法一：暴力枚举法。分析如下(以示例1为例)：

s中每一趟的结束都是覆盖完t中每一个字符，如果走到末尾还没有覆盖完，那么这个子串就是不满足要求的，想要判断覆盖完全就需要借助哈希表。

暴力解法的代码这里就不演示了，大家学习了上面几道题后应该知道何时使用滑动指针。当我们拿到一个题后想一下滑动指针是否可行，如果可以那么就不必去考虑暴力解法的代码，直接上手滑动指针的代码即可。

这道题还是用滑动指针解题，下面直接分析滑动指针为什么可行：

 和第三道题一样，这里如果用哈希表直接判断则会非常耗时，所以我们可以对更新结果的判断条件进行优化：

利用count来记录窗口内"有效字符"的种类，所谓有效字符的种类就是能和t中字符进行匹配的字符且数量可以超过p中该字符的个数。那么就可以将更新结果的判断条件改为if(count == m){}这种形式。

这道题为什么是有效字符的种类而不是有效字符的个数呢？

举个例子：假设t是"ABC"，那s中如果有AAAAAAABBBBBBBBBBC，题目要求的是覆盖完t中的所有字符，所以这种情况符合要求，所以只需看窗口内"有效字符"的种类是否和t中相等即可判断是否全部覆盖。

代码实现(C++，时间复杂度O(N))：

//滑动窗口
class Solution {
public:string minWindow(string s, string t) {int hash1[130]={0};//所有字符个数不会超过130个,用数组模拟哈希表int kinds = 0; //记录t中字符的种类for(auto e:t){if(hash1[e] == 0)++kinds;hash1[e]++;  //用hash1记录t中每个单词出现的频次}int hash2[130]={0}; //记录窗口内每个字符的频数int count = 0; //记录窗口内有效字符的个数int begin = -1,minlen = INT_MAX;//记录符合要求的最短长度以及对应的起始位置for(int left=0,right=0;right<s.size();++right){hash2[s[right]]++; //进窗口if(hash2[s[right]] == hash1[s[right]])  //维护count++count;//判断while(count == kinds){//更新if(count == kinds){if(minlen > right-left+1){minlen=right-left+1;begin = left;}}//出窗口if(hash2[s[left]] == hash1[s[left]])--count;hash2[s[left++]]--;}}  if(begin == -1)return "";elsereturn s.substr(begin,minlen);   }
};

(完结)