双指针大概来说分为两类：
- 1 快慢指针
- 2 左右指针（同向指针和双向指针）
- 1 先找扩大右端端点，直到找到符合要求的答案
- 2 求解逻辑
- 3 收缩左端点，收缩左端点是为了重新找到符合要求的答案。
1 滑动窗口原理
滑动窗口的三要素：- 1 扩大窗口，处理窗口逻辑
- 1.1 移入窗口字符
- 1.2 扩大窗口
- 1.3 窗口内数据更新
- 2 缩小窗口，处理窗口逻辑
- 2.1 移出窗口字符
- 2.2 缩小窗口
- 2.3 窗口内数据更新
- 3 明细在扩大窗口还是缩小窗口时处理返回逻辑。
/* 滑动窗口算法框架 */
void slidingWindow(string s) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 我想记录窗口中的元素和，就用 int
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c)
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d)
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}2 真题演练
2.1 最小覆盖子串
给你一个字符串s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
class Solution {
public:
string minWindow(string s, string t) {
int left = 0, right = 0, valid=0;
int start = 0, len = INT_MAX;
unordered_map<char, int> need, windows;
for(auto c:t) need[c]++;
while(right < s.size()){
// 1.1 移入窗口字符
char c = s[right];
// 1.2 扩大窗口
right++; // 索引
// 1.3 窗口内数据更新
if (need.count(c)){
windows[c]++;
if (need[c] == windows[c])
valid++;
}
while(valid == need.size()){
// 3 更新最小覆盖子串结果
if (right - left < len){
len = right - left;
start = left;
}
// 3.1 移出窗口字符
char d = s[left];
// 3.2 缩小窗口
left++;
// 3.3 窗口内数据更新
if (need.count(d)){
if (need[d] == windows[d])
valid--;
windows[d]--;
}
}
}
return len == INT_MAX? "":s.substr(start, len);
}
};2.2 字符串的排列
给你两个字符串s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> need, windows;
int left = 0, valid = 0;
for(auto c: s1) need[c]++;
for(int right=0; right<s2.size(); right++){
char c = s2[right];
if (need.count(c)){
windows[c]++;
if (need[c] == windows[c])
valid++;
}
// 1 保持住字符串存在
while(valid == need.size()){
// 2 判断字符串是否为排列
if (right - left + 1 == s1.size())
return true;
char d = s2[left];
left++;
if (need.count(d)){
if (need[d] == windows[d])
valid--;
windows[d]--;
}
}
}
return false;
}
};2.3 找到字符串中的所有异位词
给定两个字符串s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int left = 0, right = 0, valid = 0;
vector<int> result;
unordered_map<char, int> need, windows;
for(auto c:p) need[c]++;
while(right < s.size()){
char c = s[right];
right++;
if (need.count(c)){
windows[c]++;
if (windows[c] == need[c])
valid++;
}
while(valid == need.size()){
if (right - left == p.size())
result.push_back(left);
char d = s[left];
left++;
if (need.count(d)){
if (windows[d] == need[d])
valid--;
windows[d]--;
}
}
}
return result;
}
};2.4 最长无重复子串
给定一个字符串s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> my_map;
int left = 0;
int result = 0;
for(int right = 0; right < s.size(); right++){
char c = s[right];
my_map[c]++;
// 1 保持住无重复字符
while(my_map[c] > 1){
char d = s[left];
left++;
my_map[d]--;
}
// 2 获取最长子串
result = max(result, right-left+1);
}
return result;
}
};