【C++算法】滑动窗口

长度最小的子数组

题目链接：

209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/description/

• 算法原理

• 代码步骤：

1. 设置left=0，right=0
2. 设置sum=0，len=0
3. 遍历left与right向右移动
4. 记录每次的sum，并于target比较
5. 当sum>=target时，记录此时的len，结束right的循环。
6. 当right到达size的时候结束。

• 代码展示

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, len = 0;int n = nums.size();//出窗口for(int left = 0, right = 0; left < n && right < n; left++){//进窗口for(; right < n; right++){sum += nums[right];if(sum >= target){if(len == 0){len = right - left + 1;}else{len = min(len, right - left + 1);}break;}}//将出窗口的值减去if(right < n && left < n)sum = sum - nums[left] - nums[right];}return len;}
};

无重复字符的最长子 串

题目链接：

无重复字符的最长子串https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int n = s.size();//使用数组模拟一个哈希表int hash[128] = { 0 };//记录长度int len = 0;for(int left = 0, right = 0; right < n; right++){//判断窗口是否出现与s[right]重复元素if(!hash[s[right]]){//没有出现重复元素hash[s[right]]++;}else{//出现重复元素while(left <= right){//判断窗口里有无和s[right]重复元素if(hash[s[right]]){//有重复元素hash[s[left++]]--;}else{//没有重复元素hash[s[right]]++;break;}}}//记录长度并比较上次长度len = max(len, (right - left + 1));}return len;}
};

最大连续1的个数 III

题目链接：

最大连续的1的个数 IIIhttps://leetcode.cn/problems/max-consecutive-ones-iii/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution 
{
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0, zeroNums = 0, len = 0;int n = nums.size();//进窗口while(right < n){if(!nums[right]) zeroNums++;while(zeroNums > k){if(!nums[left++]) zeroNums--;}right++;len = max(len, right - left);}return len;}
};

将 x 减到 0 的最小操作数

题目链接：

将 x 减到 0 的最小操作数https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution {
public:int minOperations(vector<int>& nums, int x) {int left = 0, right = 0, sum = 0, len = -1;int n = nums.size();for(auto e : nums){sum += e;}int target = sum - x;if(target < 0) return len;sum = 0;while(right < n){sum += nums[right];while(sum > target){sum -= nums[left++];}if(sum == target){len = max(len, right - left + 1);}right++;}if(len == -1) return len;return n - len;}
};

水果成篮

题目链接：

水果成篮https://leetcode.cn/problems/fruit-into-baskets/description/

• 算法原理

• 代码步骤：

• 代码展示

方法一：哈希表

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> hashi;int ret = 0;for(int left = 0, right = 0; right < fruits.size() ; right++){hashi[fruits[right]]++;while(hashi.size() > 2){hashi[fruits[left]]--;if(hashi[fruits[left]] == 0) {hashi.erase(fruits[left]);}left++;}ret = max(ret, right - left + 1);}return ret;}
};

方法二：数组

class Solution {
public:int totalFruit(vector<int>& fruits) {int hashi[100001] = { 0 };int ret = 0;int kinds = 0;for(int left = 0, right = 0; right < fruits.size() ; right++){if(hashi[fruits[right]] == 0){kinds++;}hashi[fruits[right]]++;while(kinds > 2){hashi[fruits[left]]--;if(hashi[fruits[left]] == 0) {kinds--;}left++;}ret = max(ret, right - left + 1);}return ret;}
};

找到字符串中所有字母异位词

题目链接：

找到字符串中所有字母异位词https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char, int> hashi1, hashi2;for(auto e : p){hashi1[e]++;}int len = p.size();vector<int> ret;for(int left = 0, right = 0, count = 0; right < s.size(); right++){hashi2[s[right]]++;if(hashi2[s[right]] <= hashi1[s[right]]){count++;}if(count == len){ret.push_back(left);}if(right - left + 1 == len){if(hashi2[s[left]] <= hashi1[s[left]]){count--;}hashi2[s[left]]--;left++;}}return ret;}
};

串联所有单词的子串

题目链接：

串联所有单词的子串https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hashi1;for(auto& e : words){hashi1[e]++;}int len = words[0].size();int n = words.size();for(int i = 0; i < len; i++){unordered_map<string, int> hashi2;for(int left = i, right = i, count = 0; right + len <= s.size(); right += len){string in = s.substr(right, len);hashi2[in]++;if(hashi1.count(in) && hashi2[in] <= hashi1[in]){count++;}if(right - left + 1 > n * len){string out = s.substr(left, len);if(hashi1.count(out) && hashi2[out] <= hashi1[out]){count--;}hashi2[out]--;left += len;}if(count == n){ret.push_back(left);}}}return ret;}
};

最小覆盖子串

题目链接：

最小覆盖子串https://leetcode.cn/problems/minimum-window-substring/description/

• 算法原理

• 代码步骤：

• 代码展示

class Solution {
public:string minWindow(string s, string t) {int hashi1[128] = { 0 };int minlen = INT_MAX;int kinds = 0;int begin = -1;for(auto e : t){hashi1[e]++;if(hashi1[e] == 1){kinds++;}}int hashi2[128] = { 0 };for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];hashi2[in]++;if(hashi1[in] == hashi2[in]){count++;}while(count == kinds){if(right - left + 1 < minlen){begin = left;minlen = right - left + 1;}char out = s[left];if(hashi2[out] == hashi1[out]){count--;}hashi2[out]--;left++;}}if(begin == -1){return "";}else return s.substr(begin, minlen);}
};