滑动窗口合集

滑动窗口模板

int l = 0, r = 0, sum = 0, windSize = -1;
while(r < n){
    sum += nums[r ++];
    while(sum > target && l < n) sum -= nums[l ++];
    if(sum == target) windSize = max(windSize, r - l);
}

1658. 将 x 减到 0 的最小操作数

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int SUM = accumulate(nums.begin(), nums.end(),0);
        if(SUM < x) return -1;

        int target = SUM - x;
        int l = 0, r = 0, sum = 0, windSize = -1;
        while(r < nums.size()){
            sum += nums[r ++];
            // while(sum < target && r < nums.size()) sum += nums[r ++];
            while(sum > target && l < nums.size()) sum -= nums[l ++];
            if(sum == target) windSize = max(windSize, r - l);
        }
        
        return windSize == -1 ? -1: nums.size() - windSize;
    }
};

2516. 每种字符至少取 K 个

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符至少 k 个，返回需要的最少分钟数；如果无法取到，则返回 -1 。

示例 1：

输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。

提示：

1 <= s.length <= 105
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

C++

class Solution {
public:
    int takeCharacters(string s, int k) {
        // 要求 满足 cnt[0] >= k && cnt[1] >= k && cnt[2] >= k 的最大窗口;
        vector<int> cnt(3);
        int n = s.size();
        for(auto e: s)
            cnt[e -'a'] ++;
        if(cnt[0] < k || cnt[1] < k || cnt[2] < k) return -1;
        int l = 0, r = 0, windSize = -1;
        while(r < n){
            cnt[s[r ++]-'a'] --;
            while(l < n && cnt[0] < k || cnt[1] < k || cnt[2] < k) cnt[s[l ++] - 'a'] ++;
            if(cnt[0] >= k && cnt[1] >= k && cnt[2] >= k) windSize = max(windSize, r - l);
        }
        return windSize == -1 ? -1 : n - windSize;
    }
};

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length

C++

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        // 种类 <= 2 的最大窗口
        int l = 0, r = 0, windSize = 0;
        map<int , int> mp;
        while(r < fruits.size()){
            mp[fruits[r ++]] ++;
            while(l < fruits.size() && mp.size() > 2){
                if( -- mp[fruits[l]] == 0) mp.erase(fruits[l]);
                l ++;
            }
            windSize = max(windSize, r - l);
        }
        return windSize;
    }
};

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

C++

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> cnt1(26),cnt2(26);
        for(auto e : s1)
            cnt1[e - 'a'] ++;
        int l = 0, r =0 ,windSize = 0;
        while(r < s2.size()){
            cnt2[s2[r ++] - 'a'] ++;
            while(l < s2.size() && cnt1[s2[l] - 'a'] <  cnt2[s2[l] - 'a']) cnt2[s2[l ++] - 'a'] --;
            if(cnt1 == cnt2) return true;
        }
        return false;
    }
};

159. 至多包含两个不同字符的最长子串

给你一个字符串 s ，请你找出至多包含 两个不同字符 的最长子串，并返回该子串的长度。

示例 1：

输入：s = "eceba"
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。

示例 2：

输入：s = "ccaabbb"
输出：5
解释：满足题目要求的子串是 "aabbb" ，长度为 5 。

提示：

1 <= s.length <= 105
s 由英文字母组成

C++

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        map<char, int> mp;
        int n = s.size();
        int l = 0, r =0 ,windSize = 0;
        while(r < n){
            mp[s[r++]] ++;
            while(l < n && mp.size() > 2) {
                if(-- mp[s[l]] == 0) mp.erase(s[l]);
                l ++;
            }
            windSize = max(windSize , r - l);
        }
        return windSize;
    }
};

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

C++

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        int n = nums.size();
        set<long> st;
        int l = 0, r = 0;
        while(r< n){
            auto it = st.lower_bound(nums[r] - valueDiff); // 找到第一个 >= nums[r]-valueDiff 的迭代器
            if(it != st.end() && *it <= nums[r] + valueDiff) return true;
            st.insert(nums[r ++]);
            while(r - l > indexDiff) st.erase(nums[l ++]);
        }
        return false;
    }
};