例1

209. 長度最小的子數組

①窗口大小不固定

②求最小長度 -> ret = INT_MAX

③數組內的值都大于0， 符合單調性（sum? +=? nums[right] -> sum增大）

while里面符合條件，在里面更改ret

參考代碼

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;for(int left = 0, right = 0, sum = 0; right < nums.size(); right++){sum += nums[right];while(sum >= target){ret = min(ret, right - left + 1);sum -= nums[left++];}}return ret == INT_MAX ? 0 : ret;}
};

例2

3. 無重復字符的最長子串

while里面是不符合條件的，外面與ret比較就行

參考代碼

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int ret = 0;for(int left = 0, right = 0; right < s.size(); right++){hash[s[right]]++;while(hash[s[right]] > 1){hash[s[left++]]--;}ret = max(ret, right - left + 1);}return ret;}
};

例3

1004. 最大連續1的個數 III

[right,? left]，有效閉區間

參考代碼

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0;for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){if(nums[right] == 0) zero++;while(zero > k){if(nums[left++] == 0) zero--;}ret = max(ret, right - left + 1);}return ret;}
};

例4

轉換為求中間最大長度

如果要用注釋掉的部分，就要寫上target == 0，因為while(tmp >= target) 會left++，這里的==會導致left越界，所以分開寫較好，把滿足條件的放在外面

參考代碼

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0, ret = -1;for(auto e : nums)sum += e;int target = sum - x;if(target < 0) return -1;// if(target == 0) return nums.size();//for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++){tmp += nums[right];// while(tmp >= target)//☆☆☆☆☆// {//     if(tmp == target)//         ret = max(ret, right - left + 1);//     tmp -= nums[left++];//==的時候越界最后一次// }while(tmp > target) tmp -= nums[left++];if(tmp == target) ret = max(ret, right - left + 1);}return ret == -1 ? -1 : nums.size() - ret;}
};

例5

904. 水果成籃

后面的題都用到哈希映射

分析：哈希的臨界點是從0 -> 1 和從 1 -> 0

語法：--hash[fruits[left++]] ，看括號，里面的優先，外面括號的前置“++”，“--” 往后稍稍，所以hash的索引是fruit[left]，再是left自增，再是--hash[fruit[left]]

參考代碼

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001] = {0}, ret = 0;for(int left = 0 ,right = 0 ,count = 0; right < fruits.size(); right++){if(hash[fruits[right]]++ == 0) count++;while(count > 2)if(--hash[fruits[left++]] == 0) count--;ret = max(ret, right - left + 1);}return ret;}
};

例6

438. 找到字符串中所有字母異位詞

分析：因為是固定窗口，所以：if(right - left + 1 > p.size())用的是if，只用右移一次left

語法分析：

①代碼是全都拆開

②后置++?和后置 -- ，在這里，兩個寫一起是不對的，因為右操作數例有left，：順序是這樣的：顯示返回hash2[s[left],然后left++，然后hash2[s[left]]--，這時候left已經變大了1，導致左右兩邊left不是相同的值

③和⑤可以統一left

②③和④⑤是后置-- 和前置-- 的區別，所以判斷條件也會不同。個人覺得后置的更好直接理解

參考代碼

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[128] = {0}, hash2[128] = {0};for(auto e : p)hash1[e]++;for(int left = 0, right = 0, count = 0; right < s.size(); right++){if(++hash2[s[right]] <= hash1[s[right]]) count++;if(right - left + 1 > p.size()){// if(hash2[s[left]] <= hash1[s[left]]) count--;    1// hash2[s[left]]--;// left++;//if(hash2[s[left++]]-- <= hash1[s[left]]) count--;不對先++ 2// if(hash2[s[left]]-- <= hash1[s[left]]) count--;    3// left++;//if(--hash2[s[left++]] < hash1[s[left]]) count--;//不行   4//這里的后綴++比前置的--優先級高if(--hash2[s[left]] < hash1[s[left]]) count--;    //5left++;}if(count == p.size())ret.push_back(left);}return ret;}
};

例7

分析：對比上題就是把字符換成了字符串，那就只能用unordered_map<string, int>,

題目說了words里面的每個元素的長度相同，次數：words[0].size()

注意 left，right = i，不是=0，不然會ret是重復的數組

對于這行代碼： if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;如果hash1[in]沒有這個in，那么會自己創建一個，會浪費時間，前面加上hash1.count(in)判斷，可以減少時間的消耗

參考代碼

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> hash1;vector<int> ret;for(auto e : words)hash1[e]++;int len = words[0].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));if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;if(right - left + len - 1>= words.size() * len){string out(s.substr(left, len));if(hash1.count(out) && hash2[out]-- <= hash1[out]) count--;left += len;}if(count == words.size())ret.push_back(left);}       }return ret;}
};

例8

76. 最小覆蓋子串

①ret = min(ret, right - left + 1), begin = left;

②if(right - left + 1 < ret)? {ret = right - left + 1;begin = left;}

①②兩段代碼是有區別的： 上面不管ret是否變化，begin就會改變

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 下面的，ret變小了才會變化

依據上面的題目知道這里的left++是不能寫在里面的

if(hash2[s[left]]-- <= hash1[s[left]]) count--;left++;

注：這里是求最小長度，那么窗口肯定是變化的，肯定是while

參考代碼

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0}, hash2[128] = {0}, ret = INT_MAX, begin = -1;for(auto e : t)hash1[e]++;for(int left = 0, right = 0, count = 0; right < s.size(); right++){if(++hash2[s[right]] <= hash1[s[right]]) count++;while(count == t.size()){// ret = min(ret, right - left + 1), begin = left;if(right - left + 1 < ret){ret = right - left + 1;begin = left;}if(hash2[s[left]]-- <= hash1[s[left]]) count--;left++;}}return ret == INT_MAX ? "" : s.substr(begin, ret);}
};