两学一做的做题网站是多少优化营商环境
例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);}
};