C++滑動窗口詳解(優(yōu)選算法)
更新時間：2025年06月09日 11:00:57 作者：愛寫代碼的搗蛋鬼
這篇文章主要介紹了C++滑動窗口詳解(優(yōu)選算法),本文通過圖文實例相結(jié)合給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧
1、長度最小的子數(shù)組
思路：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑動窗口
// 1.left=0,right=0
// 2.進(jìn)窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結(jié)果)
// 總和大于等于 target 的長度最小的 子數(shù)組
int n = nums.size();
int l_r_sum = 0;
int ret_len = INT_MAX;
for(int left = 0, right = 0; right < n; right++)
{
// 進(jìn)窗口
l_r_sum += nums[right];
// 判斷
while(l_r_sum >= target)
{
// 更新結(jié)果
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、無重復(fù)字符的最長字串
思路：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑動窗口
// 1.left=0,right=0
// 2.進(jìn)窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結(jié)果)
int ret_len = 0, n = s.length();
int hash[128] = {0};
int len = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 進(jìn)窗口
hash[s[right]]++;
// 判斷是否含有重復(fù)字符
while(hash[s[right]] > 1)
{
// 有重復(fù)字符
// 出窗口
hash[s[left]]--;
left++;
len--;
}
// 更新 字串的長度
len++;
if(ret_len < len)
ret_len = len;
}
return ret_len;
}
};3.、最大連續(xù) 1 的個數(shù) III
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// 滑動窗口
// 1.left=0,right=0
// 2.進(jìn)窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結(jié)果)(max:放外面；min:放里面)
// 找出最長的子數(shù)組，0的個數(shù)不超過K個
int n = nums.size(), ret_count = 0, zero_count = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 進(jìn)窗口
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 的最小操作數(shù)
思路：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 滑動窗口
// 1.left=0,right=0
// 2.進(jìn)窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結(jié)果)(max:放外面；min:放里面)
// 找出最長的子數(shù)組，使它們的和等于 sum - x
int all_sum = 0;
for(auto & e : nums)
all_sum+=e;
int target = all_sum-x;
// 1 1 4 2 3
int max_len = -1, n = nums.size();
int max_sum = 0;
for(int left = 0, right = 0; right < n; right++)
{
// 進(jìn)窗口
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.進(jìn)窗口( += nums[right])
// 3.判斷
// 出窗口
// (4.更新結(jié)果)(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++)
{
// 進(jìn)窗口
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、串聯(lián)所有單詞的字串
思路：
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++) // 執(zhí)行 len 次
{
unordered_map<std::string, int> hash2;
for (int left = i, right = i, count = 0; right + len <= s.size(); right+=len) {
// 進(jìn)窗口
string in = s.substr(right, len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判斷
if(right - left + 1 > len * m)
{
// 出窗口 + 維護(hù) count
string out = s.substr(left, len);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
// 更新結(jié)構(gòu)
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; // 統(tǒng)計有效字符有多少種
for(auto& e : t)
{
if(hash1[e] == 0) kinds++;
hash1[e]++;
}
int hash2[128] = {0}; // 維護(hù)s
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(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);
}
};到此這篇關(guān)于C++滑動窗口的文章就介紹到這了,更多相關(guān)C++滑動窗口內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
這篇文章主要介紹了QString的常用方法(小結(jié))，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
這篇文章主要介紹了C語言實現(xiàn)的順序表功能,結(jié)合完整實例形式分析了C語言順序表的創(chuàng)建、添加、刪除、排序、合并等相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)簡單掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了C++ 轉(zhuǎn)換函數(shù)用法案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
排序算法是程序中常用的算法,下面這篇文章主要給大家介紹了關(guān)于十大排序算法的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
這篇文章主要該大家分享C語言算法抓交通肇事犯的練習(xí)，文章主要通過描述抓交通肇事犯得問題然后確定程序框架將結(jié)果運(yùn)算出來，下面來看詳細(xì)內(nèi)容吧,需要的朋友可以參考一下2022-03-03
深入Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)的詳解
本篇文章對Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++不使用變量求字符串長度strlen函數(shù)的實現(xiàn)方法
這篇文章主要介紹了C++不使用變量求字符串長度strlen函數(shù)的實現(xiàn)方法,實例分析了strlen函數(shù)的實現(xiàn)原理與不使用變量求字符串長度的實現(xiàn)技巧,需要的朋友可以參考下2015-06-06
VS2022實現(xiàn)VC++打包生成安裝文件圖文詳細(xì)歷程
本文主要介紹了VS2022實現(xiàn)VC++打包生成安裝文件圖文詳細(xì)歷程，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02![C++動態(tài)內(nèi)存分配（new/new[]和delete/delete[]）詳解](http://img.jbzj.com/images/xgimg/bcimg9.png)
C++動態(tài)內(nèi)存分配（new/new[]和delete/delete[]）詳解
這篇文章主要介紹了C++動態(tài)內(nèi)存分配（new/new[]和delete/delete[]）詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05