【C++算法】滑动窗口
长度最小的子数组
题目链接：
209. 长度最小的子数组 - 力扣（LeetCode）
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
- 算法原理
- 代码步骤：
- 设置left=0，right=0
- 设置sum=0，len=0
- 遍历left与right向右移动
- 记录每次的sum，并于target比较
- 当sum>=target时，记录此时的len，结束right的循环。
- 当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);}
};