LeetCode刷题笔记双指针滑动窗口

编程入门行业动态更新时间:2024-10-23 19:26:39

滑动窗口

滑动窗口：两个指针指向同一线性表，遍历方向相同，且两个指针起点不同，则会形成一个滑动窗口，两个指针以不同的策略移动，直到两个指针的值相等或满足其他特殊条件为止。滑动窗口代码模板如下:

int findSubArray(nums){len = nums.size(); // 数组/字符串长度int left = 0, right = 0; // 双指针，表示当前遍历的区间[left, right]，闭区间int sums = 0; // 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数int res = 0 // 保存最大的满足题目要求的 子数组/子串 长度for(right;right<len;++right){ // 当右边的指针没有搜索到 数组/字符串 的结尾, 一直移动右指针，去探索新的区间sums += nums[right]; // 增加当前右边指针的数字/字符的求和/计数while(区间[left, right]不符合题意){ // 此时需要一直移动左指针，直至找到一个符合题意的区间sums -= nums[left]; // 移动左指针前需要从counter中减少left位置字符的求和/计数++left; // 真正的移动左指针，注意不能跟上面一行代码写反} // 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串res = max(res, right - left + 1); // 需要更新结果}return res;
}

3 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

输入是一个字符串 s，输出是一个整数表示无重复最长子串的长度。

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

解析：

本题可以使用滑动窗口来解决：

首先，使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表枚举子串的起始位置，而右指针即为不包含重复字符的最长子串的结束位置。

滑动窗口右边界不断从左向右移动，同时判断由 left 和 right 构成的滑动窗口内的字符串是否含有重复字符。如果不含有重复字符，right 继续向右移动；如果刚好含有重复字符，记录当前子串的起始位置和长度，然后开始移动左边界指针 left，寻找新的不含有重复字符子串起点。移动过程中记录最短覆盖子串的起始位置和长度。

在枚举结束后，找到的最长的子串的长度即为答案。

class Solution {
public:int lengthOfLongestSubstring(string s) {int len = s.length();if(len<1){return 0;}unordered_set<char> hash;int left = 0, right = 0;int res = 0;for(;right<len;++right){// 如果存在重复元素，一直移动窗口左指针，直到移出重复元素while(hash.count(s[right])){hash.erase(s[left]);++left;}// 保存最大长度res = max(res,right-left+1);hash.insert(s[right]);}return res;}
};

76 最小覆盖子串

给定一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入是两个字符串 S 和 T，输出是一个 S 字符串的子串。

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：S 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”

解析：

本题使用滑动窗口求解，即两个指针 lsh 和 rsh 都是从最左端向最右端移动，且 lsh 的位置一定在 rsh 的左边或重合。

在本题中滑动窗口右边界指针 rsh 不断从左向右移动，同时判断由 lsh 和 rsh 构成的滑动窗口内的字符串是否覆盖了 T。如果没有覆盖，rsh 继续向右移动；如果刚好覆盖，记录当前子串的其实位置和长度，然后开始移动左边界指针 lsh，寻找新的覆盖子串起点。移动过程中记录最短覆盖子串的起始位置和长度。

另外，为了快速判别滑动窗口内的字符串是否覆盖 T，需要先统计T中字符的情况。我们使用一个哈希表存储 T 中的字符频数。注意T中重复字符的判断情况

在滑动窗口移动过程中：

移动右边界 rsh 指针根据 T 的长度找到覆盖 T 的子串移动左边界 lsh 指针更新覆盖子串的起始位置，寻找更短的覆盖子串

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> hash;for(const char ch: t){if(hash.find(ch)!=hash.end()){++hash[ch];}else{hash[ch] = 1;}}int t = 0;int lsh = 0, rsh = 0;int min_lsh = lsh, min_size = INT_MAX;for(rsh = 0;rsh<s.size();++rsh){if(hash.find(s[rsh]) != hash.end()){// 判断 t 中重复出现的字符if(--hash[s[rsh]] >= 0){++t;}// 当前滑动窗口[lsh,rsh]覆盖了 T，即 t == T.size()while(t == t.size()){// 如果出现更短的覆盖子串，更新最短覆盖子串的起始位置和长度int cur_size = rsh-lsh+1;if(cur_size < min_size){min_lsh = lsh;min_size = cur_size;}// 左边界移动过程中如果遍历到了 T 中的字符，当前覆盖字符数减少，当前遍历的字符容量增加if(hash.find(s[lsh]) != hash.end() && ++hash[s[lsh]] > 0){--t;}++lsh;}}}return min_size > s.size()?"":s.substr(min_lsh,min_size);}
};

151 翻转字符串里的单词

给定一个字符串 s ，逐个翻转字符串中的所有单词。单词前后包含多个空格

输入一个字符串，输出一个单词反转并去除多余空格的字符串

输入：s = " hello world "
输出：“world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

解析：

本题一种简单的思路将单词根据分隔符进行分割，然后按照逆序拼接，形成反转单词的字符串。根据这个思路我们要完成两个任务：

根据分隔符即本题中的空格，分割单词将分割好的单词逆序拼接

第一个任务我们可以使用滑动窗口实现 split 函数对单词进行分割。使用两个指针 lsh 和 rsh 从字符串头部出发从左向右遍历。首先移动窗口右边界指针 rsh，当 rsh 指向的元素是空格时，存在两种情况：

（1）lsh 与 rsh 相邻，即 lsh 和 rsh 都指向的是空格，这时窗口中单词长度为 0，我们直接将 lsh 移动到 rsh 的后一个位置。

（2）lsh 与 rsh 不相邻，这时窗口中就存在单词，我们计算该单词的长度为 len = rsh - lsh，并存储单词，同时将 lsh 移动到 rsh 的后一个位置作为新窗口的左边界。

最后如果 rsh==s.size() 即判断最后一个单词是否存在，我们将越界的s.size()视为一个空格即可，通过相同的方式取判断是否存在单词。

第二个任务我们可以利用栈的先入后出特性来反转单词，我们将字符串中的单词根据分隔符进行分割并存入栈中，然后将单词逐个出栈并拼接即可完成单词反转。最后要注意删除最后一个单词后的多余空格。

class Solution {
public:string reverseWords(string s) {stack<string> arr;int lsh = 0, rsh = 0;for(rsh;rsh<=s.size();++rsh){if(s[rsh]==' ' || rsh==s.size()){int len = rsh-lsh;if(len){arr.push(s.substr(lsh,len));}lsh = rsh+1;}}string res = "";while(!arr.empty()){res += arr.top();res += " ";arr.pop();}return res.erase(res.size()-1);}
};

C++不支持split函数，但是其他高级语言对字符分割都有很好的支持，所以本题从算法角度考虑可以不使用字符串分割方法主观增加本题的难度。

本题可以基于344 反转字符串的思想解决本题：

首先删除字符串头部和尾部多余的空格然后使用碰撞指针将整个字符串反转最后我们将字符串中单词逐个反转，恢复到原始单词字符顺序

在第三步的单词反转中我们要用到字符串分割相似的滑动窗口方法，用窗口取找到单词的范围，然后在该窗口内反转单词。

class Solution {
public:string reverseWords(string s) {// 删除头尾多余空格int head = 0, tail = s.size()-1;while(true){if(s[head]!=' ' && s[tail]!=' '){break;}if(s[head]==' '){++head;}if(s[tail]==' '){--tail;}}string res = s.substr(head,tail-head+1);// 删除中间多余空格for(int i = 0;i < res.size(); i++){if(res[i] == res[i + 1] && res[i] == ' '){  res.erase(res.begin() + i);i--;   //由于删除了一个空格，所以i要前移一位才能}}// 整体反转字符串head = 0, tail = res.size()-1;while(head<tail){swap(res[head++],res[tail--]);}// 反转单词int lsh = 0, rsh = 0;for(rsh;rsh<=res.size();++rsh){if(res[rsh]==' ' || rsh == res.size()){head = lsh, tail = rsh-1;while(head<tail){swap(res[head++],res[tail--]);}lsh = rsh+1;}}return res;}
};