【优选算法】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 - 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.更新结果)(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)
                {
                    // 出窗口 + 维护 count
                    string 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};       // 维护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);
    }
};