C++滑動窗口詳解(優(yōu)選算法)

更新時間：2025年06月09日 11:00:57 作者：愛寫代碼的搗蛋鬼

這篇文章主要介紹了C++滑動窗口詳解(優(yōu)選算法),本文通過圖文實例相結(jié)合給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧

1、長度最小的子數(shù)組

思路：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 滑動窗口
        // 1.left=0,right=0
        // 2.進窗口( += 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++)
        {
            // 進窗口
            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、無重復字符的最長字串

思路：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 滑動窗口
        // 1.left=0,right=0
        // 2.進窗口( += 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++)
        {
            // 進窗口
            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.、最大連續(xù) 1 的個數(shù) III

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        // 滑動窗口
        // 1.left=0,right=0
        // 2.進窗口( += 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++)
        {
            // 進窗口
            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.進窗口( += 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++)
        {
            // 進窗口
            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.更新結(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++)
        {
            // 進窗口
            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) {
                // 進窗口
                string in = s.substr(right, len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                // 判斷
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 維護 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};       // 維護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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: