双指针算法模型定义

双指针经典例题分析总结

双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

1. 问题

已知升序数组 $a$ 和 $b$ , 给定目标值 $x$

求出满足 $a_i + b_j = x$ 的下标数对 $(i，j)$

2. y 总做法简单回顾

步骤:

1. 先用暴力做法
2. 再找单调性优化为双指针

暴力做法 $O(nm)$

枚举所有情况

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(a[i] + b[j] == x)
            输出答案

双指针 $O(n+m)$

寻找单调性进行优化

尽管 $(i,j)$ 表示 $nm$ 种情况中的任一情况

这里还是定义了另一种含义:

$j = f(i):$ 对于每个 $i$, $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$

由于两个数组是升序的

所以在 $i$ 递增的时候, 发现 $j$ 是递减的(准确来说是单调不增)

$~$

举例来说:

a: 1 2 4 7
b: 3 4 6 8 9
x = 6

下标从 1 开始

$i = 1$ 时, 满足条件的 $j$ 为 3

$i = 2$ 时, 满足条件的 $j$ 为 2

$i = 3$ 时, 满足条件的 $j$ 为 1

$i = 4$ 时, 满足条件的 $j$ 为 1

$~$

总结, 在 $i$ 递增的时候, $j$ 单调不增, 满足单调性

双指针代码

for(int i = 1, j = m; i <= n; i++)
{
    while(j >= 1 && a[i] + b[j] > x) j--;   // 这里实际上使用 ai + bj <= x 来做划分
    if(j >= 1 && a[i] + b[j] == x)
        输出答案
}

思考

对于每个 $i$, 令 $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$

提问: 为什么 $j$ 要这么定义 ?

答: 因为在 $i$ 固定的前提下, 如此定义的 $j$ 最有可能满足 $a_i + b_j = x$

只需判断这一次, 就相当于判断了 $i$ 固定情况下 $j$ 的所有情况

$~$

提问: 为什么不用 $\leq$ ?

答: 可以用 $\leq$ , 这里使用哪个都不影响分析, 因为这里的分析带一点模糊性

实际上 $j$ 的具体定义为: 对于每个 $i$, 最有可能满足 $a_i + b_j = x$ 的 $j$

再具体来说, 有两种情况:

1. $j$ 表示满足 $a_i + b_j \geq x$ 的最小 $j$
2. $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$

$~$

这里指出 y 总讲解时一个不严谨的地方:

y 总在分析时用的 $\geq$, 但在代码中却用的 $\leq$, 前后不一致

所以你会在上面的举例分析中看到与视频中不一样的结果

3. 前置

定义

数组 a 元素 $a_1 \; a_2 \; \dots \; a_n$

数组 b 元素 $b_1 \; b_2 \; \dots \; b_m$

$(i,j)$ 表示下标对 $(i,j)$, 有时根据上下文表示 $a_i + b_j$

单调性/同向性

单调性和同向性应该是同一样东西, 我记得 y 总在别的视频里叫过同向性

对下标 $[1..n]$ 有两种遍历方向:

for(int i = 1; i <= n; i++)
    ...

for(int i = n; i >= 1; i--)
    ...

双指针算法的同向性

对循环变量 $i$ 和 $j$,

遍历 $i$ 时, $j$ 遍历方向不变

解释:

1. $i$ 和 $j$ 往往只初始化一次
2. $i$ 和 $j$ 遍历方向不改变

例:

for(int i = 1, j = 1; i <= n; i++)
    while(...) j++;

简单分析

找到 $(i,j)$ 和 $x$ 相等

其中, $i \in [1,n]$, $j \in [1,m]$

则需要找到 $(i,j) \in [1,n] \times [1,m]$ 与 $x$ 相等

笛卡尔积 $[1,n] \times [1,m]$ 共 $mn$ 种情况

4. 剖析

性质:

• 数组 a 升序

• 数组 b 升序

剖析过程:

1. 枚举-利用 0 条性质
2. 枚举优化-利用 1 条性质
3. 双指针-利用 2 条性质
4. 变形-问题等价变形后的双指针做法

起源: 枚举 $O(nm)$

最简单的解决办法就是枚举 $(1,1) \; \dots \; (i,j) \; \dots \; (n,m)$ 所有情况, 挨个判断是否与 $x$ 相等

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(a[i] + b[j] == x)
            输出答案

总结:

• 并未跳过任何元素
• 并未利用任何性质进行优化
• 尽管 $i$ 和 $j$ 的遍历方向不变, 但不算双指针同向性

枚举优化 $O(nm)$

优化方法:

对于每个 $i$, 找到最有可能满足 $a_i + b_j = x$ 的 $j$, 然后进行判断

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        if(a[i] + b[j] == x)        
            输出答案
        else if(a[i] + b[j] > x)    // 优化
            break;
    }

优化部分跳过了元素 $(i,j+1 \sim m)$

$~$

对代码做一个等价变形

$j$ 遍历方向: $1 \rightarrow m$

for(int i = 1; i <= n; i++)
{
    int j = 1;
    while(j <= m && a[i] + b[j] < x) j++;   // 划分为 < x 和 >= x 两部分

    if(j <= m && a[i] + b[j] == x)  // j 表示满足 ai + bj >= x 的最小 j
        输出答案
}

事实上, $j$ 还可以换个遍历方向

$j$ 遍历方向: $m \rightarrow 1$

for(int i = 1; i <= n; i++)
{
    int j = m;
    while(j >= 1 && a[i] + b[j] > x) j--;   // 划分为 > x 和 <= x 两部分

    if(j >= 1 && a[i] + b[j] == x)  // j 表示满足 ai + bj <= x 的最大 j
        输出答案
}

总结:

• 利用了数组 b 升序的性质
• 跳过了部分元素, 减少了循环次数
• 尽管进行了部分优化, 但时间复杂度依然是 $O(nm)$
• 尽管 $i$ 和 $j$ 的遍历方向不变, 但依然不算双指针同向性

双指针 $O(n+m)$

分析:

首先确定 $i$ 的遍历方向: $1 \rightarrow n$ 或 $n \rightarrow 1$

事实上, 选哪个都可以,

但由于习惯使然, 我们往往选用 $1 \rightarrow n$

for(int i = 1; i <= n; i++)
    ...

然后确定 $j$ 的遍历方向: $1 \rightarrow m$ 或 $m \rightarrow 1$

$~$

若 $j: 1 \rightarrow m$

for(int i = 1, j = 1; i <= n; i++)
{
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)
        输出答案
}

对比上一部分的代码

for(int i = 1; i <= n; i++)
{
    int j = 1;
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)  
        输出答案
}

分析:

某一时刻, 对处于循环中的 $(i,j)$:

• 若 $(i,j) = x$

  则找到答案

• $(i,j) < x$, 执行 j++

  则跳过了元素 $(i+1 \sim n,j)$

  但由于数组 a 升序, 这些元素递增, 不能判断与 $x$ 的大小关系, 显然不能跳过

• $(i,j) > x$, 执行 i++

  显然 $(i,j-1) < x$

  跳过了元素 $(i,j+1 \sim m)$ 和 $(i+1,1 \sim j-1)$

  因为双指针同向性, i++ 时的 j 不可能为 [1..j-1] 里的值

  $(i,j+1 \sim m)$ 显然大于 $x$, 可跳过

  $(i+1,1 \sim j-1)$ 与 $x$ 的关系不确定, 不能被跳过

$\therefore$ $j$ 的遍历方向不能为 $1 \rightarrow m$

如果按 y 总的方法来分析, 会比较好理解一些, 但可能不太具体

若 $j: m \rightarrow 1$

for(int i = 1, j = m; i <= n; i++)
{
    while(j >= 1 && a[i] + b[j] > x) j--;   

    if(j >= 1 && a[i] + b[j] == x)
        输出答案
}

对比上一部分的代码

for(int i = 1; i <= n; i++)
{
    int j = m;
    while(j >= 1 && a[i] + b[j] > x) j--;   

    if(j >= 1 && a[i] + b[j] == x)  
        输出答案
}

分析:

某一时刻, 对处于循环中的 $(i,j)$:

• 若 $(i,j) = x$

  则找到答案

• $(i,j) > x$, 执行 j--

  跳过了元素 $(i+1 \sim n,j)$

  $\because$ 数组 a 升序, 这些元素递增, 则显然都 $> x$

  $\therefore$ 这些元素能够跳过

• $(i,j) < x$, 执行 i++

  显然 $(i,j+1) > x$

  跳过了元素 $(i, 1 \sim j-1)$ 和 $(i+1, j+1 \sim m)$

  $(i, 1 \sim j-1)$ 显然小于 $x$, 可跳过

  $(i+1, j+1 \sim m)$ 显然大于 $x$, 可跳过

  利用了数组 a 和 b 升序这 2 条性质

所以若 $i$ 遍历方向为 $1 \rightarrow n$ 且 $j$ 遍历方向为 $m \rightarrow 1$ 时能够满足双指针同向性的要求

总结:

• 利用了数组 a 和数组 b 升序的性质
• 利用 $j = f(i)$ 的单调性跳过了大量元素进行优化

顺带一提 $i$ 的遍历方向为 $n \rightarrow 1$ 时的代码

此时 $j$ 的遍历方向需要为 $1 \rightarrow m$

for(int i = n, j = 1; i >= 1; i--)
{
    while(j <= m && a[i] + b[j] < x) j++;

    if(j <= m && a[i] + b[j] == x)
    {
        cout << i << ' ' << j << endl;
        return 0;
    }
}

思考

提问: 为什么要确定 $i$ 的遍历方向 ?

答: 事实上, 这个问题的关键不在于 $i$ 的遍历方向是什么, 而是要把 $i$ 给固定下来

在研究多因素问题时, 往往会固定其余因素, 研究单一因素对问题的影响

例如在微积分中, 研究多元函数的导数问题时, 会把其余变量看作常数, 对单一变量进行求导, 研究该单一变量对结果的影响, 这就是偏导数的概念

双指针问题也一样, 双指针意味着有两个循环变量, 即 $i$ 和 $j$

由于习惯使然, 往往会先固定 $i$, 再研究 $j$ 对问题的影响

$i$ 的遍历方向对结果往往没有影响, 而 $j$ 遍历方向对结果的影响是根据 $i$ 变化的, 一般是对称变化

变形 $O(n+m)$

原题:

已知升序数组 $a$ 和 $b$ , 给定目标值 $x$

求出满足 $a_i + b_j = x$ 的下标数对 $(i，j)$

变形题目:

给定矩阵 A, 从左到右和从上到下都递增, 寻找是否存在元素 x, 并返回下标

则可以定义矩阵元素 $A_{ij} = a_i + b_j$ 将原题转化为该题

leetcode 原题搜索二维矩阵 II

上一部分的分析思路就来自于这道题

$~$

这道题尽管是双指针做法, 但个人觉得并不算经典的双指针:

• 将 $i$ 和 $j$ 放在平等地位看待, 并不利于分析
• 未能总结一个做题模式
• 升序性质的利用并不经典
• 但是作为上一部分的图画分析会很形象, 具体参考 leetcode 这道题 两数之和 II - 输入有序数组 的分析

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < m; j++) cin >> b[j];

    for(int i = 0, j = m - 1; i < n && j >= 0;)
    {
        if(a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl;
            return 0;
        }
        else if(a[i] + b[j] > x) j--;
        else i++;
    }

    return 0;
}

分析方法可参考双指针经典例题分析总结中的第5道题

5. 总结

按照双指针算法模型定义中的定义, 对本题做个总结

$(i,j)$含义:

$(i,j)$ 指代 $a_i+b_j$

对于每个 $i$, $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$

样例:

a: 1 2 4 7
b: 3 4 6 8 9
x = 6

$i = 1$ 时, $j = 2$, 指代 1 + 4

$i = 2$ 时, $j = 2$, 指代 2 + 4

$i = 3$ 时, $j = 0$

$\dots$

答案为所有满足条件 $(i,j)$ 中与 x 相等的那个, 即 $(2,2)$

下标从 1 开始

单调性证明:

对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$

需要说明 $j^{\prime}$ 与 $j$ 的大小关系

假定 $j^{\prime} > j$

则 $j^{\prime} \geq j + 1$

根据定义可知 $a_i + b_j \leq x$ 和 $a_i + b_{j+1} > x$

则 $a_{i+1} + b_{j^{\prime}} \geq a_i + b_{j+1} > x$

这与 $j^{\prime} = f(i + 1)$ 的含义矛盾

$\therefore$ $j^{\prime} \leq j$, $j = f(i)$ 单调递减, 符合单调性

准确来说 $j = f(i)$ 单调不增, 即非严格单调递减

循环方向:

由于 $j = f(i)$ 单调递减, 所以 $j$ 的遍历方向为 $m \rightarrow 1$

代码:

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < m; j++) cin >> b[j];

    for(int i = 0, j = m - 1; i < n; i++)
    {
        while(j >= 0 && a[i] + b[j] > x) j--;

        if(j >= 0 && a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl;
            return 0;
        }
    }

    return 0;
}