定长滑动窗口--灵神题单（一刷进阶）

​
目录

第一题：2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）

按照力扣的 滑动窗口 标签刷到这题，知道是滑窗，但想了半天没想到怎么滑。
再看了下灵神给的滑动窗口题单【题单】滑动窗口（定长/不定长/多指针） 里面把这题归类为定长滑动窗口。
说是定长滑窗。那只能是 1的总数 或 0的总数 当作固定的窗口长度吧。
那就两种情况都写一下，反正都是O(n)。
窗口长度固定为0的总数，那窗口内 要被替换成0的个数，即窗口内1的个数就是结果，求最小
窗口长度固定为1的总数，那窗口内 要被替换成1的个数，即窗口内0的个数就是结果，求最小
上述两个结果都求出来，然后再求个最小，然后就通过了。
定长滑窗的具体写法是 初始窗口处理好，然后右端进一个，左端出一个。
class Solution {
public:
int minSwaps(vector& nums) {
int n = nums.size();
int count_1 = 0;// 统计一的个数
for (auto& num : nums) count_1 += num;
int count_0 = n - count_1;
int ret = n;
for (int left = 0, right = 0, count = 0; right < n; right++)
{
// 进窗口
count += nums[right];
// 判断
if (right - left + 1 >= count_1)
{
ret = min(ret, count_1 - count);
count -= nums[left++];
}
}
for (int left = 0, right = 0, count = 0; right < n; right++)
{
// 进窗口
if (nums[right] == 0)
{
count += 1;
}
// 判断
if (right - left + 1 >= count_0)
{
ret = min(ret, count_0 - count);
if (nums[left++] == 0) count -= 1;
}
}
return ret;
}
};
第二题：567. 字符串的排列 - 力扣（LeetCode）

这一道题如果想到要去使用哈希表，其实是非常的简单的，最主要的是如何想办法去优化。

检查字符串s2是否包含s1的排列。你通过hash1记录s1中每个字符的频率，并通过hash2跟踪当前窗口内字符的频率。每次滑动窗口时，更新字符的计数并检查是否满足s1的字符频率。优化点在于：1. 通过滑动窗口避免重复遍历，

1. 只对s1中出现的字符进行操作，减少不必要的计算。通过count变量追踪窗口中字符的匹配数量，避免了每次都重新计算。

class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size();
int n2 = s2.size();
if (n1 > n2)
return false; // 如果s1的长度大于s2，直接返回false
unordered_map hash1;
for (auto& e : s1)
hash1[e]++;
unordered_map hash2;
for (int left = 0, right = 0, count = 0; right < n2; right++) {
// 进窗口
char in = s2[right];
if (hash1.find(in) != hash1.end()) {
hash2[in]++;
if (hash2[in] <= hash1[in])
count++;
}
// 判断 出
if (right - left + 1 >= n1)
{
if (count == n1)
{
return true;
}
char ou = s2[left++];
if (hash1.find(ou) != hash1.end())
{
// 如果移出的字符在 s1 中出现过，更新 hash2 和 count
if (hash2[ou] <= hash1[ou])
{
count--;
}
hash2[ou]--;
}
}
}
return false;
}
};
第三题：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

这一道题其实也是非常简单的定长滑动窗口。没什么难度。就不解释了，直接给代码吧。

但是还是要给出疑问：

使用哈希表好？还是数组好？ 给出为什么？

class Solution {
public:
vector findAnagrams(string s, string p) {
int hash1[26]={0};
int m=p.size();
for(auto& e:p) hash1[e-'a']++;
int hash2[26]={0};
int n=s.size();
vector ret;
for(int left=0,right=0,count=0;rightm )
{
if(hash2[ou-'a']--<=hash1[ou-'a']) count--;
left++;
}
//更新结果
if(count==m)
{
ret.push_back(left);
}
}
return ret;
}
};
第四题：2156. 查找给定哈希值的子串 - 力扣（LeetCode）

这一道题其实也是不是很难，虽然力扣给出是困难题，但是只要了解一些数学知识，把题目的过程简化，难度连中等题都谈不上。

但这一切前提都是你对该部分数学知识了解，如果不了解，根本无思路。

推荐文章：分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理） - 力扣（LeetCode）

代码：

class Solution {
public:
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
int n=s.size();
string ret;
int h = 0; // 子串哈希值
for(int left=0,right=0;right=k)
{
if(h==hashValue)
{
ret=s.substr(left,k);
}
// 出
if(h==0) h=modulo;
h=(long long)h-(s[left++]-'a'+1)* power % modulo;
}
}
return ret;
}
};
第五题：1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（LeetCode）
看到这一题的时候我也是一头雾水，但是看过灵神写的题解，才慢慢反应过来。

灵神首先给出的是暴力求解

对于方法一，其实我开始也看不明白代码什么意思

class Solution {
public:
bool queryString(string s, int n) {
for(int i=1;i<=n;i++)
{
auto bin = bitset<32>(i).to_string();
bin = bin.substr(bin.find('1'));
if(s.find(bin) == -1) return false;
}
return true;
}
};
这里使用gtp解释一下

​

对于方法二：

直接截图看灵神的解释吧，人家写的太详细了，想的太妙了，尤其是其中的(x << 1) | (c - '0')。

但是妙归妙，还是要看完思路，自己尝试首先一下代码。

class Solution {
public:
bool queryString(string s, int n) {
unordered_set ans;
for(int i=0,m=s.size();i<m;i++)
{
int x=s[i]-'0';
if(x==0) continue;// 二进制为，继续
for(int j=i+1;x<=n;j++)
{
ans.insert(x);
if(j==m) break;
x=(x<<1) | (s[j]-'0');
}
}
return ans.size()==n;
}
};
第六题：2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）

这道题要说它简答吧，直接暴力硬写也可以写出来，但是要说它简单，但要使用滑动窗口来写，又比较麻烦。

思路好想，没什么难度，直接给代码

class Solution {
public:
int divisorSubstrings(int num, int k) {
vector v; //存放num这个数串每个位的值
int n; //代表数串每个位数的值
int num1 = num; //将num赋给num1
int res = 0;//美丽值-返回的结果
while(num1 != 0){//从个位 十位 百位...依次压入v容器中
n = num1%10;//余数
num1 = num1/10;//自除更新num1
v.push_back(n);
}
reverse(v.begin(),v.end());//逆序v容器的元素
int left = 0;//左边界
int right = k-1;//右边界 //0到k-1正好k个数
for(left,right;right<v.size();right++,left++){//滑动窗口方式模拟验证
int tmp = v[left];//初始化tmp 滑动窗口左边界代表 窗口内数串的最高位
for(int i=left+1;i<=right;i++){
tmp = tmp*10+v[i]; //模拟滑动窗口中元素组成一个数
}
if(tmp == 0)//如果为0，直接下一次循环
continue;
if(num%tmp == 0 ) {//如果可整除，美丽值结果+1
res++;
}
}
return res;//返回结果
}
};
第七题： 1984. 学生分数的最小差值 - 力扣（LeetCode）

如果是在没有思路，那不妨先让其有序。

class Solution {
public:
int minimumDifference(vector& nums, int k) {
int ret=INT_MAX;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int left=0,right=0;right<n;right++)
{
if(right-left+1==k)
{
ret=min(ret,(nums[right]-nums[left++]));
}
}
return ret;
}
};
没有解决的题目：

会员题除外

1. 统计完全子字符串 - 力扣（LeetCode）

2. 使二进制字符串字符交替的最少反转次数 - 力扣（LeetCode）

3. 存在重复元素 III - 力扣（LeetCode）

​