网站应用网站开发,淄博手机网站建设公司,vps里面设置了一下读取和写入网站无法显示了,谷歌seo推广培训班一、长度最小的子数组
1.链接
209. 长度最小的子数组 - 力扣#xff08;LeetCode#xff09;
2.描述 3.思路
本题从暴力求解的方式去切入#xff0c;逐步优化成“滑动窗口”#xff0c;首先#xff0c;暴力枚举出各种组合的话#xff0c;我们先让一个指针指向第一个LeetCode
2.描述 3.思路
本题从暴力求解的方式去切入逐步优化成“滑动窗口”首先暴力枚举出各种组合的话我们先让一个指针指向第一个然后往后逐一遍历区间也就是穷举出所有的子数组但根据题目要求当我们穷举出大于或者等于target的区间时右边指针再向后遍历穷举的结果将没有意义所以不需要再去往后走而是进行下一轮遍历前提是本题中数据全是正整数当左指针往后走一步后穷举的思路需要我们从头再走一次重复的数据此时我们对其进行优化定义一个sum值去记录区间数据就可以不需要再次遍历一次经过优化后我们会发现解题思路就变成了
定义两个左右指针一起从头往前走并且记录两个指针区间的和sumright指针往后当大于等于目标值时则停下记录长度然后left走一步进行判断是否仍然满足大于等于目标值若是满足则让left继续走当长度出现比原先短的区间时进行更新最小区间的长度left走到小于目标值时让right进行往前走直到right遍历完一遍数组这种两个指针同向一起走的思路叫做“滑动窗口” 4.参考代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0;int right 0;int sum nums[0];int len 0;while(right nums.size()){if(sum target){right;if(right nums.size())sumnums[right];}else{len len 0 ? right-left1 : min(len,right - left 1);if(len 1) break;sum-nums[left];}}return len;}
}; 二、无重复字符的最长子串
1.链接
3. 无重复字符的最长子串 - 力扣LeetCode
2.描述 3.思路
由于是对子串进行判断子串是一段连续的区间所以我们可以尝试采用滑动窗口的思路解决
满足窗口滑动的条件就是判断窗口内是否有重复字符可以利用哈希表去进行统计
当没有重复时则right往前走当有重复时则left往前这个过程中记录下最长的子串 4.参考代码
class Solution
{
public:int lengthOfLongestSubstring(string s) {if(s.size() 0){return 0;}int left 0;int right 0;int len 0;setchar hash;while(right s.size()){if((hash.insert(s[right])).second)//插入成功意味着没有重复{right;len max(len,right-left);}else//出现重复{hash.erase(s[left]);}}return len;}
}; 三、最大连续1的个数|||
1.链接
1004. 最大连续1的个数 III - 力扣LeetCode
2.描述 3.思路
可以将题意转化为在一段区间内0的数量不能超过k个利用滑动窗口去解决
当超过k个时left往前走直到将最前面的0给退出窗口没有超过时则right往前走不断扩大窗口过程中记录下窗口长度最大的值 4.参考代码
class Solution {
public:int longestOnes(vectorint nums, int k) {int left 0;int right 0;int n nums.size();int len 0;while(right n){while(right n (k ! 0 || nums[right] 1)){if(nums[right] 0){k--;}right;len max(len,right-left);}while(left n k 0){if(nums[left] 0)k;}}return len;}
}; 四、将x减到0的最小操作数
1.链接
1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode
2.描述 3.思路
我们可以先将问题转换成在数组内找到一段最长连续的子区间之和会刚好等于数组之和减去x的值
将问题变成在数组中找一段最长的连续子区间之和等于目标值的问题后我们就可以使用滑动窗口的思路去解决思路可以参考第一题“长度最小的子数组” 4.参考代码
class Solution
{
public:int minOperations(vectorint nums, int x) {int n nums.size();int sum 0;for(auto n:nums){sumn;}int target sum - x;if(target 0) return -1;//找到最长的子区间int len -1;for(int left 0,right 0,s 0; right n;right ){s nums[right];//进窗口while(s target)//出窗口{s-nums[left];}if(s target){len max(len,right-left1);}}return len -1 ? len : n-len;}
}; 五、水果成篮
1.链接
904. 水果成篮 - 力扣LeetCode
2.描述 3.思路
根据题意利用滑动窗口的思路当窗口内的水果种类超过两种时则开始出窗口过程中记录下窗口的长度利用哈希表去进行统计 4.参考代码
class Solution {
public:int totalFruit(vectorint fruits) {mapint,int hash;int ret 0;for(int left 0,right 0;rightfruits.size();right){hash[fruits[right]];while(hash.size()2){hash[fruits[left]]--;if(hash[fruits[left]] 0){hash.erase(fruits[left]);}left;}ret max(ret,right-left1);}return ret;}
}; 六、找到字符串中所有字母异位词
1.链接
438. 找到字符串中所有字母异位词 - 力扣LeetCode
2.描述 3.思路 4.参考代码
class Solution
{
public:vectorint findAnagrams(string s, string p) {int hash1[26] {0};int hash2[26] {0};for(auto c:p){hash1[c-a];}int m p.size();vectorint ret;for(int left 0,right 0,count 0; right s.size(); right){char in s[right];hash2[in - a];//入窗口if(hash2[in - a] hash1[in - a]) count;//维护countchar out s[left];if(right-left1 m)//出窗口{if(hash2[out - a] hash1[out - a]) count--;//维护counthash2[out - a]--;left;}//判断目标if(count m){ret.push_back(left);}}return ret;}
}; 七、串联所有单词的子串
1.链接
30. 串联所有单词的子串 - 力扣LeetCode
2.描述 3.思路 4.参考代码
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {int len words[0].size();unordered_mapstring,int m1;unordered_mapstring,int m2;vectorint ret;for(auto s:words) m1[s];for(int i 0;ilen;i)//以i位置为起点{for(int left i,right ilen-1,count 0; right s.size() ; rightlen)//滑动窗口{string in s.substr(right-len1,len);m2[in];//入窗口if(m2[in] m1[in]) count;//维护countif(right-left1 len*words.size())//出窗口{string out s.substr(left,len);if(m2[out] m1[out]) count--;m2[out]--;leftlen;}if(count words.size()) ret.push_back(left);}m2.clear();}return ret;}
}; 八、最小覆盖子串
1.链接
76. 最小覆盖子串 - 力扣LeetCode
2.描述 3.思路
有了前面的经验不难想到这题该怎么用滑动窗口解决根据题意分析我们知道首先将t内的字符记录到哈希表hash1中然后让滑动窗口的右侧不断的往前走直到满足题目条件即滑动窗口内的字符串包含了t内的字符此时让left往前收缩记录下最小的区间然后直到不再满足条件后让right继续往后找满足条件的子串最终记录下最短的那个子串即可当然还有如何优化哈希比较的细节需要注意以及对于如何记录下最短子串的考量
4.参考代码
class Solution {
public:string minWindow(string s, string t) {int n s.size();int hash1[128] {0};int hash2[128] {0};for(auto c : t) hash1[c];int begin -1; int len s.size()1;for(int left 0,right 0,count 0;right n;right){char in s[right];hash2[in];if(hash2[in] hash1[in]) count;while(count t.size()){if(right-left1 len){len right-left1;begin left;}char out s[left];if(hash2[out] hash1[out]) count--;hash2[out]--;}}if(begin -1) return ;else return s.substr(begin,len);}
}; 总结
本章节主要整理了关于滑动窗口的算法思想由简单到困难逐步递进整理了八道相关例题以及思路解析提供参考也可以通过链接去做
