创建门户网站,有关学风建设网站,最详细的wordpress教程,东莞网站建设分享seo算法专题二#xff1a;滑动窗口 一.长度最小的子数组#xff1a;1.思路一#xff1a;暴力解法2.思路二#xff1a;滑动窗口双指针3.GIF题目解析#xff1a;思路一#xff1a;思路二#xff1a; 二.无重复字符的最长子串#xff1a;1.思路一#xff1a;滑动窗口2.GIF题… 算法专题二滑动窗口 一.长度最小的子数组1.思路一暴力解法2.思路二滑动窗口双指针3.GIF题目解析思路一思路二 二.无重复字符的最长子串1.思路一滑动窗口2.GIF题目解析思路一 三.最大连续1的个数1.思路一滑动窗口2.GIF题目解析 四将x减小到0的最小操作数1.思路一滑动窗口2.GIF题目解析 五.水果成篮1.思路一滑动窗口2.GIF题目解析 六. 找到字符串中的所有字母的异位词1.思路一滑动窗口2.思路二滑动窗口比较优化2.GIF题目解析 七.串联所有单词的子串1.思路一滑动窗口 哈希映射2.GIF题目解析 八.最小覆盖子串1.思路一暴力解法哈希表2.思路二滑动窗口哈希表2.GIF题目解析 一.长度最小的子数组 长度最小的子数组
1.思路一暴力解法 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int num 100000;int value 0;int n nums.size();for (int i 0; i n; i){int sum 0;for (int j i; j n; j){sum nums[j];if (sum target){value sum;if (value target num (j - i 1)){num (j - i 1);}}}}if (num ! 100000)return num;return 0;}
};2.思路二滑动窗口双指针 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int sum 0;int len INT_MAX;for(int left0,right0;rightnums.size();right){sumnums[right];while(sumtarget){int len_1 right-left1;if(len_1 len)len len_1;sum-nums[left];}}return (lenINT_MAX? 0 : len);}
};3.GIF题目解析
思路一 思路二 二.无重复字符的最长子串 无重复字符的最长子串
1.思路一滑动窗口 class Solution {
public:int lengthOfLongestSubstring(string s) {int len 0;int hash[128]{0};for(int left0,right0;rights.size();right){ hash[s[right]];while(hash[s[right]]1){hash[s[left]]--;left; }len max(len,(right-left1));}return len;}
};2.GIF题目解析
思路一 三.最大连续1的个数 最大连续1的个数
1.思路一滑动窗口 class Solution {
public:int longestOnes(vectorint nums, int k) {int len 0;for(int left0,right0,zero0;rightnums.size();right){if(nums[right]0)zero;while(zero k)if(nums[left]0)zero--;len max(len,(right-left)1);}return len;}
};2.GIF题目解析 开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1走不到这些1数据导致记录连续1的个数出问题 四将x减小到0的最小操作数 将x减小到0的最小操作数
1.思路一滑动窗口 class Solution {
public:int minOperations(vectorint nums, int x) {int sum_1 0;vectorint::iterator it_1 nums.begin();while (it_1 ! nums.end()){sum_1 (*it_1);it_1;}int n nums.size();int target sum_1 - x;if(target 0){if(target0)return -1;elsereturn n;}//1.滑动窗口int sum_2 0;int ret 0;for (int left 0, right 0; right n; right){sum_2 nums[right];while (sum_2 target){if(sum_2 target)ret max(ret, (right - left) 1);sum_2 - nums[left];left;}if(sum_2 target)ret max(ret, (right - left) 1);}return (ret0? -1:n-ret);}
};2.GIF题目解析 五.水果成篮 水果成篮
1.思路一滑动窗口 class Solution {
public:int totalFruit(vectorint fruits) {int Hash[100001]{0};int n fruits.size();int len 0;for(int left0,right0,zero0;rightn;right){if(Hash[fruits[right]]0){Hash[fruits[right]];zero;}else{Hash[fruits[right]];}while(zero 2){Hash[fruits[left]]--;if(Hash[fruits[left]]0)zero--;}len max(len , (right-left)1);}return len;}
};2.GIF题目解析 六. 找到字符串中的所有字母的异位词 找到字符串中的所有字母的异位词
1.思路一滑动窗口 class Solution {
public:vectorint findAnagrams(string s, string p) {int hash1[26]{0};int len p.size();for(auto ch:p){hash1[ch -a];}int hash2[26]{0};vectorint vv;for(int left0,right0;rights.size();right){hash2[s[right] - a];if((right-left1) len){//1.判断是否相等int flag 0;for(int i0;i26;i){if(hash1[i] ! hash2[i]){flag -1;break;}}if(flag!-1)vv.push_back(left);hash2[s[left] - a]--;left;}}return vv;}
};2.思路二滑动窗口比较优化 1.我们有注意到一个问题在比较相等确定left可不可以push的时候去优化一下26次循环比较的过程。 2.可以给一个变量去控制数量的变化。 class Solution {
public:vectorint findAnagrams(string s, string p) {int hash1[26]{0};int len p.size();for(auto ch:p){hash1[ch -a];}int hash2[26]{0};vectorint vv;for(int left0,right0,count0;rights.size();right){//hash2[s[right] - a];if(hash2[s[right] - a] hash1[s[right] - a])count;if((right-left1) len){char out s[left];//出去窗口if(hash2[out-a]-- hash1[out-a])count--;}if(count len) vv.push_back(left);}return vv;}
};2.GIF题目解析 七.串联所有单词的子串 串联所有单词的子串
1.思路一滑动窗口 哈希映射 class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring,int hash1;for(auto s:words)hash1[s];int len words[0].size();int m words.size();for(int i0;ilen;i)//防止重复情况的出现{unordered_mapstring,int hash2;for(int lefti,righti,count0;rightlens.size();rightlen){string in s.substr(right,len);hash2[in];//1,进入窗口 维护countif(hash1.count(in) hash2[in] hash1[in])count;if((right-left1) (len*m)){//2.出去窗口 维护countstring out s.substr(left,len);if(hash1.count(out) hash2[out] hash1[out])count--;hash2[out]--;leftlen;}//3.数据更新if(count m) ret.push_back(left);}}return ret;}
};2.GIF题目解析 八.最小覆盖子串 最小覆盖子串
1.思路一暴力解法哈希表 class Solution {
public:string minWindow(string s, string t) {int hash1[128] { 0 };for (char ch : t){hash1[ch];}int kind t.size();int len INT_MAX;int begin 0;for (int i 0; i s.size(); i){int hash2[128] { 0 };int count 0;for (int j i; j s.size(); j){if (hash2[s[j]] hash1[s[j]] hash1[s[j]]!0)count;if (kind count){//更新数据if (j - i 1 len){len j - i 1;begin i;}}}}string vv();if (kind s.size() || len INT_MAX)return vv;vv s.substr(begin, len);return vv;}
};2.思路二滑动窗口哈希表 class Solution {
public:string minWindow(string s, string t) {int hash1[128] { 0 };int kind 0;for (char ch : t){if(hash1[ch] 0)kind;}int len INT_MAX;int begin -1;int hash2[128] { 0 };for (int left 0, right 0, count 0; right s.size(); right){//1.进入窗口维护countchar in s[right];if(hash2[in] hash1[in])count;//2.判断出窗口维护countwhile(count kind){if(right-left1 len){len right-left1;begin left;}char out s[left];if(hash2[out]-- hash1[out])count--;}}if(begin -1)return ;elsereturn s.substr(begin,len);}
};2.GIF题目解析
