数组的双指针技巧
数组中没有真正的指针，我们通常把索引当作数组中的指针取用，这样就可以在数组中也施展双指针技巧。
快慢指针技巧
删除有序数组中的重复项
- 重点在于题目要求原地删除
- 如果不要求原地删除的话可以直接new一个新的数组，把我们需要的数据填充进去。
- slow走在后面，fast走在前面，
- 保持nums[0, …, slow]的所有元素都是无重复的！
- fast在前面探路，找到一个不重复的元素就赋值给slow
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// 特例：空集
if (nums.size() == 0) {
return 0;
}
// 双指针
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
};
链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// 空链表
if (head == nullptr) {
return nullptr;
}
// 快慢指针法
ListNode* fast = head;
ListNode* slow = head;
//
while (fast != nullptr) {
if (slow->val != fast->val) {
slow->next = fast;
slow = slow->next;
}
fast = fast->next;
}
slow->next = nullptr;
return head;
}
};
在处理链表时，删除节点后需要释放其内存以避免泄漏。以下是添加内存管理的改进版本：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr) {
if (slow->val == fast->val) {
ListNode* temp = fast; // 保存待删除节点
fast = fast->next; // 移动快指针
delete temp; // 释放内存
} else {
slow->next = fast; // 链接非重复节点
slow = slow->next; // 移动慢指针
fast = fast->next; // 移动快指针
}
}
slow->next = nullptr; // 断开后续可能存在的重复节点
return head;
}
};
- 主要改进点：
- 使用ListNode* temp保持待删除的节点
- 发现重复节点时立即释放内存
移除元素
- 维护索引0到slow的数组不包含要移除的val
- 所以fast往前走，遇到了val就跳过，没遇到val就赋值给slow！
#include <vector>
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0;
// 维护slow之前(包含slow)都是无重复的
while (fast < nums.size()) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
这道题是移除val元素，为啥这里是先赋值后slow++?
- 保证nums[0…slow-1] 是不包含值为 val 的元素的
- 最后结果数组长度就是slow
移除0
#include <vector>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0;
while (fast < nums.size()) {
// 遇到0就跳过
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
// 保证了0到slow-1索引都是没有0的
// 再把后续所有元素填充为0
while (slow < nums.size()) {
nums[slow] = 0;
slow++;
}
}
};
滑动窗口——快慢双指针指针变体
两种场景：
- 遍历所有子数组
- 遍历所有字串
本质都是一样的
遍历左右边界
暴力解的情况，需要嵌套for穷举所有子数组
for (int left = 0; left < nums.size(); left++) {
for (int right = left; right < nums.size(); right++) {
// nums[left, right] 是一个子数组
}
}
暴力遍历与滑动窗口最大的区别在于，滑动窗口的两个指针都是只向前走，一步也不会退，暴力解法中的right是每次移动left后都回退到新left位置重新开始遍历的。
滑动窗口核心框架模板
- 定义窗口左右边界left和right
- 维护这个窗口
- 不断滑动
- 更新答案
// 索引区间 [left, right) 是窗口
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);
right++;
// 当需要缩小窗口
while （window needs shrink） {
// 缩小窗口
window.removeFirst(nums[left]);
}
}
- 滑动窗口只用O(n)就能穷举出所有子串么？
- NO！穷举所有子串必须要用双层for循环
- 对于大部分题目并不需要穷举所有字串
- 只需要遍历符合题目条件的窗口即可
- 滑动窗口相当于对穷举过程剪枝，避免冗余计算
- 属于算法本质中的，聪明的穷举这一类
滑动窗口难点： - 如何向窗口中添加新元素？
- 如何缩小窗口？
- 哪个阶段更新结果？
- 如何找bug等？
滑动窗口算法的代码框架
void slidingWindow(string s) {
// 用适合的数据结构记录窗口中的数据，根据具体的业务场景变通
// 比如说，想记录窗口中元素出现的次数，就需要用map
// 如果我想记录窗口中的元素和，就用int
auto window = ...
int left = 0, right = 0;
while (right < s.size()) {
// c 是将要移入窗口的字符
char c = s[right];
window.add(c);
// 增大窗口
right++;
// 进行窗口内的一系列更新
...
// *** debug 输出的位置 ***
printf("window: [%d, %d)\n", left, right);
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
// 判断左窗口是否要收缩
while (window needs shrink) {
// d就是将要移出窗口的字符
char d = s[left];
window.remove(d);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
- 代码中的两处…代表更新窗口数据的位置
- 这两处… 分别是扩大和缩小窗口的操作，完全是对称的
遇到子串/子数组的问题，只需要回答三个问题：
- 什么时候要移动right扩大窗口？窗口加入字符时，应该更新哪些数据？
- 什么时候窗口应该暂停扩大？开始移动left实现窗口缩小？从窗口移出字符时，应该更新哪些数据？
- 什么时候应该更新结果？
最小覆盖字串
lc.76
假设用暴力解法：
for () { // 遍历i
for () { // 从i+1开始遍历j
if s[i:j] 包含所有t中的字母:
更新答案
}
}
以上暴力遍历思路很直接，但是时间复杂度太高了。
下面开始设计滑动窗口
左闭右开 [ left， right）设计（主要是边界 条件处理问题）：
- 原则上双端都开，或者都闭是可以的
- 如果（left，right）双端都开：
- left，right都在开头0位置时，窗口内没有元素
- right移动到1的时候，（0，1）还是没有元素
- 如果 [ left，right ] 双端都闭：
- [0, 0]初始区间就包含了一个元素
起初 [0, 0) 没有元素
移动一步后 [0, 1) 一个元素
所以左闭右开非常符合滑窗的需求
- 不断扩大right指针，扩大窗口[left, right)，直到窗口中字符串符合要求
- 此时，停止增加right，转而不断增加left，缩小窗口，直到窗口中的字符串不再符合要求，每次增加left都需要更新答案。
- 重复以上两步，直到right到达字符串s尽头。
- 步骤2：寻找可行解
- 步骤3：优化可行解
- 最终找到最优解
初始状态：
移动右边界right，寻找可行解，直到窗口[left，right)，直到满足条件，即包含T所有字符
接着优化当前解，移动left指针，缩小[left，right)窗口，移动的过程中保证满足题目要求条件。
直到窗口字符串不再符合要求，left不再移动
之后重复上述过程，先移动right再移动left，直到right移动到s末端。
首先，初始化window和needs两个哈希表unordered_map，记录窗口中的字符和需要凑齐的字符：
unordered_map(char, int) need, window;
然后，使用left和right变量初始化窗口的两端，左闭右开，所以初始情况窗口没有包含任何元素
int left = 0;
int right= 0;
while (right < s.size()) {
// c是移动到
}
三个问题：
- 什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
- 什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
- 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
- 当一个字符c进入到窗口时，应该增加window计数器
- 如果一个字符c将要移出窗口时，应该减少window计数器
- 当valid满足need时应该收缩窗口
- 应该在收缩窗口时，更新最终结果
class Solution {
public:
string minWindow(string s, string t) {
// 两个map记录器：window 和 need
unordered_map<char, int> need;
unordered_map<char, int> window;
for (char c : t) {
need[c]++;
}
// 滑动窗口左右边界初始化
int left = 0;
int right = 0;
// 记录下window中字符满足need条件的字符个数
int valid = 0;
// 初始化答案
// 记录最小覆盖字串的起始索引以及长度
int start = 0;
int len = INT_MAX; // 初始化窗口长度为无穷大
while (right < s.size()) {
// c 是即将移入窗口的字符
char c = s[right];
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) { // 如果c是need需要的
window[c]++; // 拉入window
if (window[c] == need[c]) { // 直接对比两个map
valid++;
}
}
// 判断左窗口是否需要收缩？
while (valid == need.size()) {
// 在这里更新最小覆盖字串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是需要移出窗口的字符
char d = s[left];
left++;
// 进行窗口内数据一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
- 发现某个字符在window的数量满足了need的需要，就要更新valid，表示有一个字符已经满足要求
- 两次对窗口内数据的更新操作是完全对称的
- 当 valid==need.size() 说明 t 中所有字符都已经被完全覆盖了，已经得到了一个可行的子串，可行解，现在改优化可行解，移动左边界了！
class Solution {
public:
// 判断s1的排列之一是否是s2的子串
// 可以包含重复字符，所以难度大的
bool checkInclusion(string s1, string s2) {
// 初始化两个map，need和window
unordered_map<char, int> need;
unordered_map<char, int> window;
for (char c : s1) need[c]++;
int left = 0;
int right = 0;
int valid = 0;
while (right < s2.size()) {
char c = s2[right];
right++;
// 进行窗口内数据一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断窗口左边界是否要收缩？
while (right - left >= s1.size()) {
// 收缩前，判断是否找到了合法字串
if (valid == need.size())
return true;
// 可能要收缩的元素d
char d = s2[left];
left++;
// 进行窗口内的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return false;
}
};
- 本题与最小覆盖字串那道题几乎一模一样
- 区别在于
- 本题移动left缩小窗口的时机是窗口大于s1的长度时，因为题意要求的排列，所以长度需要一致
- 当发现valid==need.size()时，说明窗口中就是一个合法的排列，所以立即返回true。
- 至于如何处理窗口的扩大与缩小，和上一题完全相同。