刷题日记–滑窗法力扣1658将x减到0的最小操作数题解classSolution{public:intminOperations(vectorintnums,intx){intsum0;intnnums.size();for(inta:nums)suma;inttargetsum-x;if(target0)return-1;intret-1;for(intleft0,right0,ssum0;rightn;right){ssumnums[right];while(ssumtarget){ssum-nums[left];}if(ssumtarget){retmax(ret,right-left1);}}if(ret-1)returnret;elsereturnnums.size()-ret;}};解题思路力扣904水果成篮题解classSolution{public:inttotalFruit(vectorintfruits){intans0,left0;unordered_mapint,intcnt;for(intright0;rightfruits.size();right){cnt[fruits[right]];// fruits[right] 进入窗口while(cnt.size()2){// 不满足要求intoutfruits[left];cnt[out]--;// fruits[left] 离开窗口if(cnt[out]0){cnt.erase(out);}left;}ansmax(ans,right-left1);}returnans;}};解题思路力扣438找到字符串中所有字母异位词题解classSolution{public:vectorintfindAnagrams(string s,string p){vectorintret;inthash1[26]{0};for(autoch:p)hash1[ch-a];inthash2[26]{0};intmp.size();//字符串的长度窗口大小的临界值for(intleft0,right0,count0;rights.size();right){charins[right];if(hash2[in-a]hash1[in-a])count;if(right-left1m){charouts[left];if(hash2[out-a]--hash1[out-a])count--;}if(countm)ret.push_back(left);}returnret;}};解题思路力扣30串联所有单词的子串题解classSolution{public:vectorintfindSubstring(string s,vectorstringwords){vectorintret;unordered_mapstring,inthash1;for(autos:words)hash1[s];intlenwords[0].size(),mwords.size();//len是单个单词长度m是单词字符串数组的长度//把单个单词想象成一个字母有效单词个数有效字母个数进行化简for(inti0;ilen;i){unordered_mapstring,inthash2;for(intlefti,righti,count0;rightlens.size();rightlen){string ins.substr(right,len);hash2[in];if(hash1.count(in)hash2[in]hash1[in])count;if(right-left1len*m){string outs.substr(left,len);if(hash1.count(out)hash2[out]--hash1[out])count--;leftlen;}if(countm)ret.push_back(left);}}returnret;}};解题思路力扣76最小覆盖子串题解classSolution{public:stringminWindow(string s,string t){//left,lenintreal0;intlens.size();intmt.size();intret_left0;unordered_mapchar,inthash1;for(autoch:t)hash1[ch];unordered_mapchar,inthash2;for(intleft0,right0,count0;rights.size();right){charins[right];hash2[in];if(hash1.count(in)hash2[in]hash1[in])count;if(countm){real1;while(countm){charouts[left];if(hash1.count(out)hash2[out]hash1[out])count--;hash2[out]--;}if(lenright-left1){ret_leftleft-1;lenright-ret_left1;}}}s.substr(ret_left,len);if(real)returns.substr(ret_left,len);elsereturn;}};解题思路