滑动窗口9.23

1876.长度为3且各字符不同的子字符串

1876. 长度为三且各字符不同的子字符串 - 力扣（LeetCode）https://leetcode.cn/problems/substrings-of-size-three-with-distinct-characters/?envType=list&envId=24zW97w8自写思路：
数组充当哈希表，只要当前窗口等于3判断该数组中是否有某处值大于1，如果有则说明某一个字母连续出现两次。
如果没有则使res自增，每次循环时会自动删掉第一个数然后放新数进来
一开始是想用unordered set去写，后来写完了才想起来这个set无法存相同的字符

子字符串是连续的，不要忘记这一点，所以这也是使用滑动窗口约束字符串的原因

这道题固定了窗口大小，并且很明显的判断子串是否各不相同是应用哈希表来查重，属于哈希和窗口搭配的模板题了，虽然简单不过可以多看几遍熟练掌握

class Solution {
public:
    int countGoodSubstrings(string s) {
        int arr[26]={0};
        int res=0;
        for(int i=0;i<s.size();i++){
            if(i>2)arr[s[i-3]-'a']--;
            arr[s[i]-'a']++;
            if(fun(arr)&&i>=2)res++;
        }
        return res;
    }
    bool fun(int *arr){
        for(int i=0;i<26;++i)
        if(arr[i]>1)return false;
        return true;
    }
};

这是一道暴力求解貌似比滑动窗口效率要高的题，官方提供的是暴力求解的方法

class Solution {
public:
    int countGoodSubstrings(string s) {
        int res = 0;
        int n = s.size();
        for (int i = 0; i < n - 2; ++i){
            if (s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]){
                ++res;
            }
        }
        return res;
    }
};
 

 用滑动窗口空间是ON，而暴力是O1，时间都一样

---

1984.学生分数的最小差值

1984. 学生分数的最小差值 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/?envType=list&envId=24zW97w8

这道题相当于k就是窗口大小，求窗口内最大值和最小值的差然后比较谁最小，但是，前提是得排序，如果你不排序，你将无法确定窗口的大小是多少，它是一个不确定的数
因为数据杂乱无章，以题给例子为例，这个例子里能减出最小值的两个数是在该数组的最左和最右，那你就得不停扩大窗口，试探性找本次最小差

这也就相当于把窗口大小看成是数组的总大小，通过有规律的使k个数相减，通过循环来控制，以求得最小值，看上去好像可行，但是如果k不是2呢？
你要同时控制多重k循环，来使相减数有规律的往后推，以保证不要落下任何可能的值，实际上这是无法做到的。

说完了排序的必要，还要说一下，这个循环的必要
一开始没有看懂，觉得这已经排完序了，那你就直接用nums【i+k-1】-nums【i】不就完事了？但是它确实不一定是最小的数
比如说这个排完序的数组【0，9，12，13】它不一定就是最后一个数往前减就大！
虽然题目说的是任意取k个，但是我们已经排完序了，所以把它看成是在窗口里取数，不然排序的意义何在？
 

这道题也是窗口的一个应用，自己没有做出来，一开始找窗口范围，发现是无法求得窗口的范围的，这让我犯了难，看了题解发现，将数组排序就可以用已给条件k来确定了

如果对于可以进行排序并且感觉可以用窗口做的题，不妨试一下排序，问题就会迎刃而解

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());int res=INT_MAX;
        for(int i=0;i<=nums.size()-k;++i){
            res=min(res,nums[i+k-1]-nums[i]);
        }
        return res;
    }
};

---

2269.找到一个数字的K美丽值

2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）https://leetcode.cn/problems/find-the-k-beauty-of-a-number/?envType=list&envId=24zW97w8把数字num转化为字符串，进入循环使i一直指向窗口末端，使用i-k+1定位窗口左端，窗口大小恒定为k，截取该窗口字符串转化为数字若该数字不为0且可以被整除，则res自增

这道题很简单，没什么要讲的，就是用窗口确定该次要判断的字符串长度，然后将其转为数字再进行整除运算，如果能整除则res++，挨个窗口往后走即可。

代码也是十分的简单

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s=to_string(num);int res=0;
        for(int i=k-1;i<s.size();i++){
            int sum=stoi(s.substr(i-k+1,k));
            if(sum&&num%sum==0)res++;
        }
        return res;
    }
};

---

下一期我们更新哈希表，如果对你有帮助请给个三连支持一下哦！

想看更多的算法题解或者数据结构也可以查看往期的文章，如果你有想看的也可以在评论区进行讨论