1.长度最小的子数组
解法一：暴力解法
时间复杂度：O(N^2)
算法思路：
从前往后枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个「起始位置」开始，然 后寻找⼀段最短的区间，使得这段区间的和「⼤于等于」⽬标值。 将所有元素作为起始位置所得的结果中，找到最⼩值即可。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 记录结果int ret = INT_MAX;int n = nums.size();// 枚举出所有满⾜和⼤于等于target的⼦数组 [start, end]// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start = 0; start < n; start++){int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++){sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满⾜条件时{// 更新结果，start开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};解法二：滑动窗口
时间复杂度:O(N)
算法思路：
由于此问题分析的对象是「一段连续的区间」，因此可以考虑「滑动窗口」的思想来解决这道题。
让滑动窗口满足：从 i 位置开始，窗口内所有元素的和小于 target（那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度）。
做法：将右端元素划入窗口中，统计出此时窗口内元素的和：
- 如果窗口内元素之和大于等于 target：更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件）
- 如果窗口内元素之和不满足条件：right++，另下一个元素进入窗口。
为何滑动窗⼝可以解决问题，并且时间复杂度更低？
-
这个窗口寻找的是：以当前窗口最左侧元素（记为 left1）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满足区间和 sum >= target 时的最右侧（记为 right1）能到哪里。
-
我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 left1。但是如果继续像方法一一样，重新开始统计第二个元素（left2）往后的和，势必会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的）。
-
此时，right1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从 right1 这个元素开始，往后找满足 left2 元素的区间（此时 right1 也有可能是满足的，因为 left1 可能很小。sum 剔除掉 left1 之后，依旧满足大于等于 target）。这样我们就能省掉大量重复的计算。
-
这样我们不仅能解决问题，而且效率也会大大提升。
时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O (N)。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0,right = 0;int n = nums.size();int sum = 0;int len = INT_MAX;for(left = 0,right = 0;right<n;right++){sum+=nums[right];//进窗口while(sum>=target)//判断{len = min(len,right-left+1);sum-=nums[left];//出窗口left++;}}return len==INT_MAX?0:len;}
};2.无重复字符的最长字串
算法一：暴力解法
算法思路： 枚举从每⼀个位置开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即可。 在往后寻找⽆重复⼦串能到达的位置时，可以利⽤哈希表统计出字符出现的频次，来判断什么 时候⼦串出现了重复元素。
//暴力解法
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0; // 记录结果int n = s.length();// 1. 枚举从不同位置开始的最长重复子串// 枚举起始位置for (int i = 0; i < n; i++) {// 创建一个哈希表，统计频次int hash[128] = { 0 };// 寻找结束为止for (int j = i; j < n; j++) {hash[s[j]]++; // 统计字符出现的频次if (hash[s[j]] > 1) { // 如果出现重复的break;}// 如果没有重复，就更新retret = max(ret, j - i + 1);}}// 2. 返回结果return ret;}
};算法二：
算法思路： 研究的对象依旧是⼀段连续的区间，因此继续使⽤「滑动窗⼝」思想来优化。 让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。
做法：右端元素 left进⼊窗⼝的时候，哈希表统计这个字符的频次： 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝， 直到 left这个元素的频次变为 1 ，然后再更新结果。 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果。
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int left = 0,right = 0,n = s.size();int ret = 0;while(right<n){hash[s[right]]++;//进窗口while(hash[s[right]]>1)//判断{hash[s[left++]]--;//出窗口}//更新ret = max(ret,right-left+1);right++;}return ret;}};3.最大连续1的个数III
类似这种连续区间，我们可以考虑使用滑动窗口
算法思路：滑动窗口
初始化一个计数器；初始化一些变量 left = 0，right = 0，ret = 0；
当right小于数组大小的时候，一直有以下循环
让当前元素进入窗口，同时要统计0的个数：如果0的数量超过了k，那么我们需要让左侧元素滑出窗口，顺便更新我们的计数器,直到我们的计数器恢复为小于k。
然后right继续向后走，处理下一个元素。
循环结束后，ret 存的就是最终结果。
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0,right = 0,n = nums.size();int count = 0;//计数int ret = 0;while(right<n){if(nums[right]==0){count++;}while(count>k)//判断0的数量是否合法{if(nums[left++]==0)//出窗口{count--;}}ret = max(ret,right-left+1);right++;//入窗口}return ret;}
};4.将x减到0的最小操作数
算法思路:滑动窗口,时间复杂度O(N)
转化问题：
将问题转化为求 target = sum(nums) - x。
如果 target < 0，问题无解，return -1。
初始化：
左右指针 left = 0，right= 0（滑动窗口区间表示为 [l, r]，左右区间是否开闭很重要，必须设定与代码一致）。
记录当前滑动窗口内数组和的变量 sum = 0。
记录当前满足条件数组的最大区间长度 maxLen = -1。
循环条件：
进窗口
当 r 小于等于数组长度时，一直循环：
如果 sum < target，右移右指针，直至变量和大于等于 target，或右指针已经移到头。
出窗口
如果 sum > target，右移左指针，直至变量和小于等于 target，或左指针已经移到头。
等于target时才会更新
如果经过前两步的左右移动使得 sum == target，维护满足条件数组的最大长度，并让下个元素进入窗口。
循环结束后：
如果 maxLen 的值有意义，则计算结果返回；否则，返回 -1。
class Solution {
public:int minOperations(vector<int>& nums, int x) {int left = 0, right = 0;int n = nums.size();int len = -1;int sum = 0;for(int i = 0;i<n;i++){sum+=nums[i];}int target = sum-x;if(target<0) return -1;sum = 0;while(right<n){sum+=nums[right];//进窗口while(sum>target)//出窗口{sum-=nums[left++];}if(sum==target){len = max(len,right-left+1);}right++;}return len==-1?len:n-len;}
};5.水果成蓝
这道题目，我们先来思考一下暴力解法，暴力解法的思路比较简答，给一个hash表统计每一个水果出现了多少种，就是把所有符合要求的长度都枚举出来，取最长的即可。
然后讲解一下为什么要用滑动窗口来解决：
滑动窗口解题思路：
a.初始化哈希表hash来统计窗⼝内⽔果的种类和数量；
b. 初始化变量：左右指针left=0，right=0，记录结果的变量ret=0；
c. 当right⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
i. 将当前⽔果放⼊哈希表中；
ii. 判断当前⽔果进来后，哈希表的⼤⼩：
•
如果超过2：
将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
如果这个元素的频次减⼀之后变成了0，就把该元素从哈希表中删除；
重复上述两个过程，直到哈希表中的⼤⼩不超过2；
iii. 更新结果ret；
iv. right++，让下⼀个元素进⼊窗⼝；
d. 循环结束后，ret存的就是最终结果。
这个长度是有限制的，所以我们这里直接用一个自定义一个hash数组就行了，可以提高一点效率。
class Solution {
public:int totalFruit(vector<int>& fruits) {// 用于记录每种水果出现的频次，数组大小设为一个较大值，因为水果种类的值范围已经给定，这里设为100001int hash[100001] = {0}; int ret = 0;int n = fruits.size();// 滑动窗口的左右指针，kind用于记录当前窗口内水果的种类数for (int left = 0, right = 0, kind = 0; right < n; right++) {// 当新水果进入窗口时if (hash[fruits[right]] == 0) {kind++;}hash[fruits[right]]++;// 如果窗口内水果种类超过2种while (kind > 2) {// 将左指针指向的水果移出窗口hash[fruits[left]]--;if (hash[fruits[left]] == 0) {kind--;}left++;}// 更新最长符合条件的子数组长度ret = max(ret, right - left + 1);}return ret;}
};6.找到字符串中所有字母异位词
算法思路：滑动窗口（定长滑窗）
时间复杂度O(N)
因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构 造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p 的异位词；
因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个 数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
class Solution {
public:vector<int> findAnagrams(string s, string p) {int len = p.size();int hash1[26] = { 0 };for (auto ch : p){hash1[ch - 'a']++;}int len1 = len;vector<int> vt;int left = 0, right = 0;int hash2[26] = { 0 };while (right < s.size()){hash2[s[right] - 'a']++;//进窗口if (right - left + 1 > len)//出窗口{hash2[s[left] - 'a']--;left++;}if (right - left + 1 == len)//判断{int i = 0;while (hash1[i++] == hash2[i]){if (i == 25){vt.push_back(left);break;}}}right++;}return vt;}
};小优化：
我们这里给一个count 来统计窗口当中有效字符个数。
class Solution {
public:vector<int> findAnagrams(string s, string p) {int len = p.size();int hash1[26] = { 0 };//统计字符串p中出现的字符个数for (auto ch : p){hash1[ch - 'a']++;}int count = 0;//vector<int> vt;int left = 0, right = 0;int hash2[26] = { 0 };//统计窗口中每一个字符出现的个数while (right < s.size()){hash2[s[right] - 'a']++;//进窗口if(hash2[s[right]-'a']<=hash1[s[right]-'a']){count++;}if (right - left + 1 > len){if(hash2[s[left]-'a']<=hash1[s[left]-'a']){count--;}hash2[s[left] - 'a']--;//出窗口left++;}if (count==len){vt.push_back(left);}right++;}return vt;}
};7.串联所有子串
算法思路：滑动窗口（同上题）
时间复杂度 O(N)
如果我们把每⼀个单词看成⼀个⼀个字⺟，问题就变成了找到「字符串中所有的字⺟异位词」。⽆ ⾮就是之前处理的对象是⼀个⼀个的字符，我们这⾥处理的对象是⼀个⼀个的单词。
代码：
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;//保存word里面所有单词的频次for(auto& s:words){hash1[s]++;}vector<int> vt;int len = words[0].size(),m = words.size();for(int i = 0;i<len;i++){unordered_map<string,int> hash2;//统计窗口内单词的频次for(int left = i,right = i,count = 0;right+len<=s.size();right+=len){//进窗口string 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){vt.push_back(left);}}}return vt;}
};8.最小覆盖字串
做题思路：
最开始想的是和之前一样用哈希表统计两个字符串中的字母数量，然后用滑动窗口在该区间内对比。这题我们依然可以发现left左移，right不用右移，所以自然可以想到用滑动窗口解题。
滑动窗口的套路都差不多，但是这里如果用count优化时，需要处理好count的数量，不像之前，我们的hash[out]<=hash[out]，count--即可，因为这里我们出窗口的时候，窗口内的有效字母是可以重复的，需要特别注意一下。
附加代码：
#include <iostream>
#include <string>
#include <unordered_map>class Solution {
public:std::string minWindow(std::string s, std::string t) {std::unordered_map<char, int> hash1;// 存储目标字符串 t 中字符及其出现的次数for (auto& c : t) {hash1[c]++;}std::string str;int len = t.size();int minLen = INT_MAX, ret = 0;std::unordered_map<char, int> hash2;for (int left = 0, right = 0, count = 0; right < s.size(); right++) {// 进窗口char in = s[right];hash2[in]++;// 如果当前字符是目标字符串中的字符，并且其出现次数不超过目标字符串中的次数，增加计数if (hash1[in]&&hash2[in] <= hash1[in]) {count++;}// 判断是否满足包含 t 中的所有字符while (count == len) {ret = right - left + 1;if (ret < minLen) {minLen = ret;str = s.substr(left, ret);}// 出窗口char out = s[left];hash2[out]--;// 如果出窗口的字符是目标字符串中的字符，并且其出现次数小于目标字符串中的次数，减少计数if (hash1[out]&&hash2[out] < hash1[out]) {count--;}left++;}}return str;}
};优化思路：
这里发现用count统计字母有效数量对比起来似乎有点麻烦，其实可以发现，我们只需要统计有效字母的种类。比如hash1中A的数量有3个，那么只有当hash2中A的数量等于3时，我们的count才会++，为什么不大于的时候也加呢,大于不也是有效的吗，大于的时候我们的count会多加的，比如在下图中这个例子中，大于等于的话，B会让count加2次，但这时count的数量是符合去判断的，但窗口里只有ABB，是不符合覆盖子串的，记住，我们统计的是种类，不是数量，那么出窗口的时候也是同理，在出窗口前，如果hash2[out]==hash1[out]时count才会--,我们这里的判断条件是count == hash.size();
class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };int hash2[128] = { 0 };int kinds = 0;//计算hash1的大小for (auto ch : t){if (hash1[ch]++ == 0)kinds++;}int minlen = INT_MAX, begin = -1;for (int left = 0, right = 0, count = 0; right < s.size(); right++){ //count用来统计有效字符的种类，不是数量。//进窗口char in = s[right];if (++hash2[in] == hash1[in])//维护count{count++;}while (count == kinds)//判断{if (right - left + 1 < minlen)//更新{minlen = right - left + 1;begin = left;}char out = s[left];if (hash2[out]-- == hash1[out])//出窗口{count--;}left++;}}return begin == -1 ? "" : s.substr(begin, minlen);}
};
int main() {Solution sol;std::string s = "ABBCA";std::string t = "ABC";std::string result = sol.minWindow(s, t);std::cout << result << std::endl;return 0;
}