GabWiki双指针
常见问题分类：
- 对于一个序列，用两个指针维护一段区间。
- 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作。
C++
for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(i, j)) ++j;
// 具体问题的逻辑
}for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(i, j)) ++j;
// 具体问题的逻辑
}滑动窗口
Java
void slidingWindow(char[] s) {
int n = s.length;
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < n) {
char curr = s[right++];
window.put(curr, window.getOrDefault(curr, 0) + 1);
// 更新窗口内数据
// ...
// 判断窗口是否需要收缩
while (窗口需要收缩) {
// 在窗口每次收缩前更新答案
// ...
curr = s[left++];
window.put(curr, window.getOrDefault(curr, 0) - 1);
// 更新窗口内数据
// ...
}
// 在窗口收缩后更新答案
// ...
}
}void slidingWindow(char[] s) {
int n = s.length;
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < n) {
char curr = s[right++];
window.put(curr, window.getOrDefault(curr, 0) + 1);
// 更新窗口内数据
// ...
// 判断窗口是否需要收缩
while (窗口需要收缩) {
// 在窗口每次收缩前更新答案
// ...
curr = s[left++];
window.put(curr, window.getOrDefault(curr, 0) - 1);
// 更新窗口内数据
// ...
}
// 在窗口收缩后更新答案
// ...
}
}C++
void sliding_window(string s) {
int n = s.length();
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < n) {
char curr = s[right++];
++window[curr];
// 更新窗口内数据
// ...
// 判断窗口是否需要收缩
while (窗口需要收缩) {
// 在窗口每次收缩前更新答案
// ...
curr = s[left++];
--window[curr];
// 更新窗口内数据
// ...
}
// 在窗口收缩后更新答案
// ...
}
}void sliding_window(string s) {
int n = s.length();
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < n) {
char curr = s[right++];
++window[curr];
// 更新窗口内数据
// ...
// 判断窗口是否需要收缩
while (窗口需要收缩) {
// 在窗口每次收缩前更新答案
// ...
curr = s[left++];
--window[curr];
// 更新窗口内数据
// ...
}
// 在窗口收缩后更新答案
// ...
}
}