> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：熟练掌握滑动窗口算法，并且能把下面的题目做出
> 毒鸡汤：人生就像一场马拉松比赛，不是看谁跑得最快，而是看谁坚持到最后。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
而今天我们的板块是双指针问题。
⭐知识讲解
滑动窗口本质上是两个指针所固定一个窗口而这个窗口可以移动。
⭐经典题型
🌙topic-->1
题目原型：. - 力扣（LeetCode）
题目分析：
在数组中中找出最短的距离，而这个区间的数字之和要大于等于target
讲解算法原理：
编写代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int n = nums.size();
int sum = 0;
int len = INT_MAX;
for(int left = 0,right = 0; right < n; right++)
{
// 进窗口
sum = sum + nums[right];
// 判断
while(sum >= target)
{
// 更新结果
len = min(len,right- left + 1);
// 出窗口
sum = sum - nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};细节注意：
1.有可能数组没有我们的值，这里我们len就最开始定义成最大值
2.如果没有最大值我们返回0
🌙topic-->2
题目原型：. - 力扣（LeetCode）
题目分析：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
讲解算法原理：
编写代码：
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
// 使用数组来模拟哈希表
int hash[128] = {0};
// 定义窗口左右端
int left = 0;
int right = 0;
// 计算字符串长度
int n = s.size();
int ret = 0;
// 循环
while(right < n)
{
// 存入hash表中，进入窗口
hash[s[right]]++;
// 判断
while(hash[s[right]] > 1)
{
// 出窗口
hash[s[left++]]--;
}
// 计算结果
ret = max(ret,right - left + 1);
// 让下一个元素进入
right++;
}
// 返回
return ret;
}
};🌙topic-->3
题目原型：. - 力扣（LeetCode）
题目分析：
在一个数组中，元素只有 1 和 0 ，给定一个K值，这个K值是可以在数组中改变 0 的个数的多少，在改变数组时，需要求出连续 1 的最长值
讲解算法原理：
编写代码：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
vector<int> P(n + 1);
for (int i = 1; i <= n; ++i) {
P[i] = P[i - 1] + (1 - nums[i - 1]);
}
int ans = 0;
for (int right = 0; right < n; ++right) {
int left = lower_bound(P.begin(), P.end(), P[right + 1] - k) - P.begin();
ans = max(ans, right - left + 1);
}
return ans;
}
};🌙topic-->4
题目原型：. - 力扣（LeetCode）
题目分析：
可以减去左右数组的元素值，找出满足最小值的减的次数
讲解算法原理：
编写代码：
class Solution {
public:
int minOperations(vector<int>& nums, int x)
{
// 先计算数组和的大小
int sum = 0;
for(int a : nums)
sum = sum + a;
int target = sum - x;
// 细节处理
if(target < 0)
return -1;
int ret = -1;
for(int left = 0,right = 0,tmp = 0;right < nums.size();right++)
{
// 进窗口
tmp = tmp + nums[right];
// 判断
while(tmp > target)
{
// 出窗口
tmp = tmp - nums[left++];
}
// 更新结果
if(tmp == target)
ret = max(ret,right - left + 1);
}
if(ret == -1)
return ret;
else
return nums.size() - ret;
}
};🌙topic-->5
题目原型：904. 水果成篮 - 力扣（LeetCode）
题目分析：
可以采摘最多棵水果树，保证最多两种水果种类（必须是连续的）
讲解算法原理：
编写代码：
class Solution {
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = {0}; // 统计每种水果的个数
int ret = 0; // 计算最多水果个数
for(int left = 0,right = 0,kinds = 0;right < f.size();right++)
{
// 维护水果种类
if(hash[f[right]] == 0)
kinds++;
// 进窗口
hash[f[right]]++;
while(kinds > 2) // 判断
{
// 出窗口
hash[f[left]]--;
if(hash[f[left]] == 0)
kinds--;
left++;
}
// 更新结果
ret = max(ret,right - left + 1);
}
return ret;
}
};🌙topic-->6
题目原型：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
题目分析：
在 s 中返回跟 p 异位词的索引，不可缺少。
讲解算法原理：
编写代码：
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret; // 用数组来存储结果
// 第一个hash桶来存储 p 字符串
int hash1[26] = { 0 };
int m = p.size();
for(auto e: p) // 存入
hash1[e - 'a']++;
// 第二个hash桶来存储每个字符出现的次数
int hash2[26] = { 0 };
int count = 0; // 计算字符种类次数
for(int left = 0,right = 0;right < s.size();right++)
{
char in = s[right];
// 进窗口
hash2[in - 'a']++;
// 维护字符种类
if(hash2[in - 'a'] <= hash1[in - 'a'])
count++;
// 判断
if(right -left + 1 > m)
{
char out = s[left++];
// 维护字符种类
if(hash2[out - 'a'] <= hash1[out - 'a'])
count--;
// 出窗口
hash2[out - 'a']--;
}
// 更新结果
if(count == m)
ret.push_back(left);// 尾插
}
return ret;
}
};
🌙topic-->7
题目原型：30. 串联所有单词的子串 - 力扣（LeetCode）
题目分析：
在 s 中找区间，这个区间必须是连续的，s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
讲解算法原理：
编写代码：
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret; // 用来保存结果
unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
for (auto& s : words)
hash1[s]++;
int len = words[0].size(), m = words.size();
for (int i = 0; i < len; i++) // 执⾏ len 次
{
unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
for (int left = i, right = i, count = 0; right + len <= s.size();
right += len)
{
// 进窗⼝ + 维护 count
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;
}🌙topic-->8
题目原型：76. 最小覆盖子串 - 力扣（LeetCode）
题目分析：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
讲解算法原理：
编写代码：
class Solution
{
public:
string minWindow(string s, string t)
{
int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for (auto ch : t)
if (hash1[ch]++ == 0) kinds++;
int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
int minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while (count == kinds) // 判断条件
{
if (right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
}
}
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
