算法】"/>
专题二:滑动窗口【优选算法】
滑动窗口:
什么时候用? 同向双指针(找单调性)
怎么用?
1)用left、right指针维护窗口
2)进窗口(right指针++,更新窗口内的值)
3)判断
出窗口(left++,并更新窗口内的值)
4)更新结果(注意每道题更新结果的时机不同,需具体分析)
目录
滑动窗口:
1、长度最小的子数组
2、无重复字符的最长子串
3、最大连续1的个数
4、将x减到0的最小操作数
5、水果成篮
6、找到字符串中所有字母异位词
7、串联所有单词的子串(容器的使用)
8、最小覆盖子串
1、长度最小的子数组
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int sum = 0,len = INT_MAX;for(int l = 0,r = 0;r < n;r++){sum += nums[r];//入窗口while(sum >= target)//判断{len = min(len,r - l + 1);//更新结果sum -= nums[l++];//出窗口}} return len == INT_MAX?0:len; }
};
2、无重复字符的最长子串
暴力解法,枚举每一个字串,但分析可发现,出现重复字符时,left可直接跳到重复字符,right也无需往回走。因此就是同向双指针,也就是滑动窗口。
class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> hash(128);//用来判断字符是否出现过int len = 0,n = s.size();for(int l = 0,r = 0;r < n;r++){//进窗口hash[s[r]]++;while(hash[s[r]] > 1)//判断{hash[s[l]]--;//出窗口l++;}len = max(len,r-l+1);//更新结果}return len;}
};
3、最大连续1的个数
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int count = 0;int ret = 0;for(int left = 0,right = 0;right < n;right++){//进窗口if(nums[right] == 0) count++;while(count > k)//判断if(nums[left++] == 0)count--;//出窗口ret = max(ret,right-left+1);//更新结果}return ret;}
};
4、将x减到0的最小操作数
通过正难则反,可以将此题转换成类似第一题
class Solution {
public:int minOperations(vector<int>& nums, int x) {int n = nums.size();int sum = 0;for(auto x : nums){sum += x;}int target = sum - x;if(target < 0) return -1;int ret = -1,sum2 = 0;for(int left = 0,right = 0;right < n;right++){sum2 += nums[right];while(sum2 > target) sum2 -= nums[left++];if(sum2 == target) ret = max(ret,right - left + 1);}return ret == -1?-1:n - ret;}
};
5、水果成篮
unordered_map版
class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int,int> hash;int n = fruits.size();int kind = 0,ret = 0;for(int left = 0,right= 0;right < n;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 - left + 1);}return ret;}
};
数组版:
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100010] = {0};int n = fruits.size();int kind = 0,ret = 0;for(int left = 0,right= 0;right < n;right++){if(hash[fruits[right]] == 0) kind++;hash[fruits[right]]++;while(kind > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0) kind--;left++;}ret = max(ret,right - left + 1);}return ret;}
};
6、找到字符串中所有字母异位词
check的优化:
class Solution {
public:vector<int> findAnagrams(string s, string p) {int hashp[265] = {0};for(auto x : p) hashp[x]++;int count = 0;vector<int> ret;int hashs[256] = {0};for(int l = 0,r = 0;r < s.size();r++){hashs[s[r]]++;if(hashs[s[r]] <= hashp[s[r]]) count++;if(r - l + 1 > p.size()){if(hashs[s[l]] <= hashp[s[l]]) count--;hashs[s[l]]--;l++;}if(count == p.size()) ret.push_back(l);}return ret;}
};
7、串联所有单词的子串(容器的使用)
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;vector<int> ret;for(auto& s:words){hash1[s]++;}int len = words[0].size(),m = words.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){//进窗口+维护countstring in = s.substr(right,len);hash2[in]++;if(hash2[in] <= hash1[in]) count++;//判断if(right - left + 1 > len * m) {//出窗口+维护countstring out = s.substr(left,len);if(hash2[out] <= hash1[out]) count--; hash2[out]--;left += len;}//更新结果if(count == m) ret.push_back(left);}}return ret;}
};
8、最小覆盖子串
class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0};int kinds = 0;//统计有效字符种类数for(auto ch : t) {if(hash1[ch] == 0) kinds++;hash1[ch]++;}int hash2[128] = {0};int minlen = INT_MAX,begin = -1;for(int left = 0,right = 0,count = 0;right < s.size();right++){//进窗口char in = s[right];hash2[in]++;if(hash2[in] == hash1[in]) count++;while(count == kinds){if(right - left+1 < minlen){minlen = right - left + 1;begin = left;}char out = s[left++];if(hash2[out] == hash1[out]) count--;hash2[out]--;}}if(begin == -1) return "";else return s.substr(begin,minlen);}
};
更多推荐
专题二:滑动窗口【优选算法】
发布评论