第一讲 基础算法 - 06 双指针算法

A18 双指针（尺取法）_哔哩哔哩_bilibili
A19 双指针 P1381 单词背诵_哔哩哔哩_bilibili
A20 双指针 [ABC098D] Xor Sum 2_哔哩哔哩_bilibili

---

双指针算法

1 核心思想

对于以往需要双重 for 循环暴力解的题目进行优化
eg: 在快排和归并排序中都用到了双指针的思想。

所以一般做题都是先用暴力解法想思路，再用双指针优化时间复杂度。

2 分类

• 第 1 类双指针算法：一个指针操作一个序列（归并排序的合并步骤）
• 第 2 类双指针算法：两个指针操作同一个序列（快速排序）

3 模板

for (int i = 0, j = 0; i < n; i ++ ){
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

说明：

• 目的是把 O(n2) 复杂度降为 O(n)
• 双指针算法会把序列分成 3 段，理解各段的含义很重要（尤其第2段）
  • 第1段：0 ~ j - 1
  • 第2段：j ~ i
  • 第3段：i + 1 ~ n - 1

4 应用

4.1 AcWing

1. AcWing 799. 最长连续不重复子序列 * | Akari的小站

2. AcWing 800. 数组元素的目标和 | Akari的小站

3. AcWing 2816. 判断子序列 | Akari的小站

4.2 洛谷

1. A18 双指针（尺取法）_哔哩哔哩_bilibili

2. A19 双指针 P1381 单词背诵_哔哩哔哩_bilibili

3. A20 双指针 [ABC098D] Xor Sum 2_哔哩哔哩_bilibili