双指针

核心

• 用两个变量（指针）在数组或链表上按一定规则移动
• 将某些暴力 $O(n^2)$ 的枚举优化到 $O(n)$
• 可配合单调双端队列使用

重要问题

• 移动安全：保证不会错过最优解
• 移动条件：什么条件下移动指针
• 结束条件：什么条件下结束指针移动

常见用法

左右指针（对撞指针）

两个指针从线性表两端开始，向中间移动，直到满足某种条件（如相遇）。

应用： 两数和、反转数组、回文、接雨水

例题

---

快慢指针

两指针同向移动，但移动速度或启动时机不同。

应用： 链表中点、环链表、有序数组原地去重

例题

---

同向双指针（滑动窗口）

两指针维护一个区间，左指针负责收缩区间、右指针负责扩展区间。

步骤

• 不满足条件：尝试适应条件
• 满足条件：贪心找最优

实现方式

假设r++是迁就条件，l++是找最优解。

1. 先想办法满足条件，满足后再贪心

while(!satisfy) r++;
l++;

2. 如果满足条件则贪心，否则尝试满足

if(satisfy) l++;
else r++;

应用： 区间和、区间极值、最大覆盖子串

例题参见单调双端队列笔记

---

例题

两数之和

给定int数组nums[]和一个目标值tar，找出和为tar的两个整数，返回所有可能下标。

使数组单调递增，使用对撞指针

• 左指针右移会使和减小
• 右指针左移会使和增大

// 排序
sort(nums.begin(), nums.end());
// 左右指针
int l = 0, r = nums.size() - 1;
// 未相遇
while(l < r){
    // 和小移左指针
    if(nums[l] + nums[r] > tar) l++;
    else{
        // 等于目标值记录
        if(nums[l] + nums[r] == tar) 
            ans.emplace_back(l, r);
        // 移右指针
        r--;
    }
}

有序数组去重

给定有序int数组nums[]，去除重复元素，返回去重后的数组。

设$n$个元素，$m$个不重复，有$m\lt n$ 将数组前$m$个位置用不重复元素覆盖

• 快指针扫描数组
• 慢指针覆写数组

// 快慢指针
int l = 0, r = 0;
// 快指针未到末尾
while(r < nums.size()){
    // 出现不重复元素
    if(nums[r] != nums[l]){
        // 覆写下一个位置
        l++; // 一定要先右移
        nums[l] = nums[r];
    } 
    // 继续扫描
    r++;
}