> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握滑动窗口算法，并且能把下面的题目做出
> 毒鸡汤：人生就像一场马拉松比赛，不是看谁跑得最快，而是看谁坚持到最后。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题。
而今天我们的板块是双指针问题。
⭐知识讲解
滑动窗口本质上是两个指针所固定一个窗口而这个窗口可以移动。
⭐经典题型
🌙topic-->1
题目原型：.
题目分析：
在数组中中找出最短的距离，而这个区间的数字之和要大于等于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
题目原型：
题目分析：
给定一个字符串 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
题目原型：
题目分析：
在一个数组中，元素只有 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
题目原型：
题目分析：
可以减去左右数组的元素值，找出满足最小值的减的次数
讲解算法原理：
编写代码：
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
题目原型：
题目分析：
可以采摘最多棵水果树，保证最多两种水果种类（必须是连续的）
讲解算法原理：
编写代码：
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
题目原型：
题目分析：
在 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
题目原型：
题目分析：
在 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
题目原型：
题目分析：
给你一个字符串 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); } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
