【优选算法】C++滑动窗口

1、长度最小的子数组

思路：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 滑动窗口// 1.left=0,right=0// 2.进窗口( += nums[right])// 3.判断//      出窗口// (4.更新结果)// 总和大于等于 target 的长度最小的 子数组int n = nums.size();int l_r_sum = 0;int ret_len = INT_MAX;for(int left = 0, right = 0; right < n; right++){// 进窗口l_r_sum += nums[right];// 判断while(l_r_sum >= target){// 更新结果int len = right - left + 1;if(len < ret_len)ret_len = len;// 出窗口l_r_sum -= nums[left++];}}return ret_len==INT_MAX?0:ret_len;}
};

2、无重复字符的最长字串

 思路：

class Solution {
public:int lengthOfLongestSubstring(string s) {// 滑动窗口// 1.left=0,right=0// 2.进窗口( += nums[right])// 3.判断//      出窗口// (4.更新结果)int ret_len = 0, n = s.length();int hash[128] = {0};int len = 0;for(int left = 0, right = 0; right < n; right++){// 进窗口hash[s[right]]++;// 判断是否含有重复字符while(hash[s[right]] > 1){// 有重复字符// 出窗口hash[s[left]]--;left++;len--;}// 更新 字串的长度len++;if(ret_len < len)ret_len = len;}return ret_len;}
};

3.、最大连续 1 的个数 III

 

class Solution {
public:int longestOnes(vector<int>& nums, int k) {// 滑动窗口// 1.left=0,right=0// 2.进窗口( += nums[right])// 3.判断//      出窗口// (4.更新结果)(max:放外面；min:放里面)// 找出最长的子数组，0的个数不超过K个int n = nums.size(), ret_count = 0, zero_count = 0;for(int left = 0, right = 0; right < n; right++){// 进窗口if(nums[right] == 0)zero_count++;// 判断是否超过 k 个while(left < n && zero_count > k){// 出窗口if(nums[left++] == 0)zero_count--;}ret_count = max(ret_count, right-left+1);}return ret_count;}
};

4、将 x 减到 0 的最小操作数

 思路：

class Solution {
public:int minOperations(vector<int>& nums, int x) {// 滑动窗口// 1.left=0,right=0// 2.进窗口( += nums[right])// 3.判断//      出窗口// (4.更新结果)(max:放外面；min:放里面)// 找出最长的子数组，使它们的和等于 sum - xint all_sum = 0;for(auto & e : nums)all_sum+=e;int target = all_sum-x;// 1  1  4  2  3int max_len = -1, n = nums.size();int max_sum = 0;for(int left = 0, right = 0; right < n; right++){// 进窗口max_sum += nums[right];// 判断while(left < n && max_sum > target) // 先比它大{// 出窗口max_sum -= nums[left++];}   if(max_sum == target)   // 后判断相等max_len = max(right-left+1, max_len);}return max_len==-1?-1:n-max_len;}
};

5、水果成篮

 思路：

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> hash;       int n = fruits.size();int 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;}
};

6、找到字符串中是所有字母异位词(*)

思路：

class Solution {
public:vector<int> findAnagrams(string s, string p) {// 滑动窗口// 1.left=0,right=0// 2.进窗口( += nums[right])// 3.判断//      出窗口// (4.更新结果)(max:放外面；min:放里面)vector<int> ret_vector;int hash_s[26] = {0};int hash_p[26] = {0};for(auto& xp : p)hash_p[xp-'a']++;int n = s.size();for(int left = 0, right = 0; right < n; right++){// 进窗口hash_s[s[right]-'a']++;// 判断两个 hash 是否相同while(right - left + 1 > p.size()){// 出窗口hash_s[s[left]-'a']--;left++;}if(HashSame(hash_s, hash_p))// 两个hash 相同ret_vector.push_back(left);}return ret_vector;}bool HashSame(int* hash_s, int* hash_p){for(int i = 0; i < 26; i++){if(hash_s[i] != hash_p[i])return false;}return true;}
};

7、串联所有单词的字串

思路：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<std::string, int> hash1;for (auto& str : words) {hash1[str]++;}int len = words[0].size(), m = words.size();for (int i = 0; i < len; i++) // 执行 len 次{unordered_map<std::string, int> hash2;for (int left = i, right = i, count = 0; right + len <= s.size(); right+=len) {// 进窗口string in = s.substr(right, len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) count++;// 判断if(right - left + 1 > len * m){// 出窗口 + 维护 countstring out = s.substr(left, len);if(hash1.count(out) && 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& e : t){if(hash1[e] == 0) kinds++;hash1[e]++;}int hash2[128] = {0};       // 维护sint 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(kinds == count){if(right - left + 1 < minlen){minlen = right - left +1;begin = left;}char out = s[left++];if(hash2[out] == hash1[out]) count--;hash2[out]--;}}if(minlen == INT_MAX) return "";else return s.substr(begin, minlen);}
};