滑动窗口

定义

滑动窗口的是这样一类问题的求解方法，在数组上通过双指针同向移动( 维护一个固定的区间)而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。

使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。

题目链接：

Leetcode 219. 存在重复元素 II
Leetcode 643. 子数组最大平均数 I
Leetcode 1763. 最长的美好子字符串
Leetcode 1876. 长度为三且各字符不同的子字符串
Leetcode 1984. 学生分数的最小差值
Leetcode 2269. 找到一个数字的 K 美丽值
Leetcode 2379. 得到 K 个黑块的最少涂色次数

第一题

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= $10^5$
-$10^9$ <= nums[i] <= $10^9$
0 <= k <= $10^5$

思路：

只需要用一个哈希表来记录数组中的每一个元素，以及该元素的下标。
当发现元素nums[i] 已经存在了，那么只需要判断当前元素 nums[i] 的下标 i
与 前一个nums[i] 元素的下标 map[nums[i]] 相差是否超过k。

代码

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int,int> mp;
        for(int i = 0;i < n;i++){
            if(mp.count(nums[i])){
                if(i - mp[nums[i]] <= k) return true;
            }
            mp[nums[i]] = i;
        }
        return false;
    }
};

时间复杂度：O(N)

第二题

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 $10^{-5}$ 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

n == nums.length
1<= k <= n <= $10^5$
-$10^4$ <= nums[i] <= $10^4$

思路：

用两个指针 i 和 j 维护 k个元素的区间
用一个sum 记录当前k个元素的和
当i 和 j 之间的元素 超过 k的时候 指针 i 就向后移动，sum 减去nums[i]
否则的话 指针j 就向后移动 sum 加上 nums[j]
用一个变量 ans 记录在这个过程中最大的 平均值，最后返回答案即可

代码

 class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        //记录 k 个元素的和
        double sum = 0;
        //求最大平均值 所以初始的时候 只要初始为一个非常小的值即可
        double ans = -1e9;

        for(int i = 0,j = 0;j < n;j++){
            sum += nums[j];
            //当此时的区间超过k时 指针i就向后移动 sum 减去nums[i](因为此时的nums[i] 已经不属于这个k区间了)
            if(j - i + 1 > k) sum -= nums[i++];
            //当区间内的元素正好为k 并且此时的平均值 大于 ans 就更新ans
            if(j - i + 1 == k && ans < sum/k) ans = sum / k;
        }
        return ans;
    }
};

时间复杂度：O(N)

第三题

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，“abABB” 是美好字符串，因为 ‘A’ 和 ‘a’ 同时出现了，且 ‘B’ 和 ‘b’ 也同时出现了。然而，“abA” 不是美好字符串因为 ‘b’ 出现了，而 ‘B’ 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = “YazaAay”
输出：“aAa”
解释：“aAa” 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 ‘a’
和大写形式 ‘A’ 也同时出现了。 “aAa” 是最长的美好子字符串。

示例 2：

输入：s = “Bb”
输出：“Bb”
解释：“Bb” 是美好字符串，因为 ‘B’ 和 ‘b’ 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = “c”
输出：“”
解释：没有美好子字符串。

示例 4：

输入：s = “dDzeE”
输出：“dD”
解释：“dD” 和 “eE” 都是最长美好子字符串。 由于有多个美好子字符串，返回 “dD”
，因为它出现得最早。

提示：

1 <= s.length <= 100
s 只包含大写和小写英文字母。

思路：

我们可以枚举字符串中每一个起始位置，从该位置开始寻找美好字符串。在这个过程中我们只需要不断更新美好字符串的长度即可（取最大值），还要更新起始位置。
关键是怎么快速判断该字串是美好字符串（要求大小写字母都存在）

代码

class Solution {
public:
    string longestNiceSubstring(string s) {
       int n = s.size();
       //pos 记录起始位置   len记录最长美好子串的长度
       int pos = -1,len = 0;
       for(int i = 0;i < n;i++){
           int a = 0,b = 0;
           for(int j = i;j < n;j++){
               char c = s[j];
               //如果是小写字母 记录在a上面
               if(c >= 'a' && c <= 'z') a |= 1 << (c - 'a');
               //大写字母 就记录到b上面
               else b |= 1 << (c - 'A');
               //a == b 说明大小写字母都出现了 j - i + 1 > len 说明此时的美丽子串的长度大于记录的长度 这样才更新起点 和 最大长度
               if(a == b && j - i + 1 > len){
                   len = j - i + 1;
                   pos = i;
               }
           }
       }
       return pos == -1 ? "" : s.substr(pos,len);
    }
};