顾名思义，双指针就是左右指针同时枚举，有点类似于滑动窗口
可以这样辨别一下：窗口大小变化的是双指针，窗口大小固定的是滑动窗口
但是基本上可以不用区分，叫啥都可以，本质是一样的
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。
- 枚举右端点
- 哈希表记录当前字符出现个数
int lengthOfLongestSubstring(string s) {
int n = s.size(), ans = 0;
int left = 0, right = 0;
unordered_map<char, int> mp; // 维护字符出现次数
for (right = 0; right < n; ++ right) {
char c = s[right];
mp[c] += 1;
// 当前字符出现次数多余 1 次就需要右移左端点直到次数为 1 次
while (mp[c] > 1) {
-- mp[s[left++]];
}
ans = max(ans, right-left+1);
}
return ans;
}其实哈希表可以直接记录当前字符最后出现的位置，这样避免一直移动左端点，可以节省时间
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。
- 枚举右端点 right，维护 [left, right] 之间的元素和
- 如果元素和大于 target，就右移左端点
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int left = 0, right = 0;
int sum = 0;
int ans = n + 1; // INT_MAX
for (right = 0; right < n; ++ right) {
sum += nums[right];
/* while (sum - nums[left] >= target) {
sum -= nums[left];
++ left;
}
if (s >= target) ans = min(ans, right-left+1); */
// 比较好理解的写法：直接在条件的区间里面计算 ans
while (sum >= target) {
ans = min(ans, right-left+1);
sum -= nums[left];
++ left;
}
}
return ans;
}给你一个整数数组
nums和一个整数k，请你返回子数组内所有元素的乘积严格小于k的连续子数组的数目。
- 和前一题同理，枚举右端点，维护区间元素的乘积
- 注意边界情况以及 k=1 的特判
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size();
int left = 0, right = 0;
int ans = 0;
int m = 1; // 维护 [left, right] 各个元素的乘积
if (k <= 1) return 0; // 特判, [1,1,1] k=1
for (right = 0; right < n; ++ right) {
m *= nums[right];
while (m >= k) {
m /= nums[left];
++ left;
}
// 以 right 结尾的子数组中 m < k 的个数为 right-left+1
// [left, right] [left+1, right] [right, right]
ans += right - left + 1;
}
return ans;
}| 题目 | 说明 | 题解 |
|---|---|---|
| 76. 最小覆盖子串 | 通过哈希表 needHash 判断滑动窗口包含了T的所有元素，使用 needCnt 免除每次遍历哈希表 🔥 | 滑窗 |
| 395. 至少有 K 个重复字符的最长子串 | 直接双指针无法解决，加入枚举目标串字符种类数 [1, 26]条件 就可以让区间具有二段性 🔥，另外可以用分治递归求解 |
宫水三叶 |
| 1004. 最大连续1的个数 III | 维护区间 0 的个数，找出一个最长的子数组，该子数组内最多允许有 K 个 0（正难则反） | 负雪明烛 |
| 1234. 替换子串得到平衡字符串 | 待替换子串之外的任意字符的出现次数都不能超过 m = n/4，维护区间外的字符出现次数 | 0x3F |
| 1438. 绝对差不超过限制的最长连续子数组 | 维护区间内最大值和最小值的差值，使用底层是红黑树的有序集合 multiset | 负雪明烛 |
| 1658. 将 x 减到 0 的最小操作数 | 和 2516 类似，逆向思考更直观，正向思考须分前缀后缀考虑 | 0x3F |
| 2379. 得到 K 个黑块的最少涂色次数 | 最基本的滑动窗口，窗口大小固定 | 通过 |
| 2516. 每种字符至少取 K 个 | 正向思考需要先考虑前缀为空，然后枚举前缀，反向思考更容易理解，直接滑动窗口取中间的字符至多x个 | 双指针 滑窗 |
总结
- 双指针的题目需要知道维护什么，比如维护区间的元素和、元素乘积或者0的个数
- 有时候正向难考虑就可以逆向思考，正难则反
- 有时根据题目条件无法沟站区间的二段性，这时候可以考虑加入隐含条件，让区间具有二段性，例如 LC.395
- 有些题目难以找到左边界右移的条件，例如 LC.76，需要两层思考：窗口是否满足要求以及如何判断
其他
| 题目 | 说明 | 题解 |
|---|---|---|
| 6355. 统计公平数对的数目 | 排序之后，维护双指针出和的大小 | 题解 |
这里题目和一般的滑动窗口不太一样，就是单纯的双指针，两个指针一个在左端，一个在右端，然后两个指针向中点移动。