我的算法书 - 双指针算法：优雅地优化循环

摘要

双指针（Two Pointers）是一种简单而强大的算法技巧，它通过在数据结构（通常是数组或链表）上维护两个指针，并根据特定条件移动它们，从而将嵌套循环的复杂度优化到线性级别。本文将深入探讨双指针的核心思想，并通过“指定和的整数对”、“判断回文串”和“寻找区间和”等经典问题，展示双指针在不同场景下的应用模式及其代码实现。

背景与动机

在处理数组或序列问题时，我们最直接的思路往往是使用嵌套循环。例如，要在一个数组中寻找两个数，使它们的和等于目标值，一个 for 循环嵌套另一个 for 循环似乎是不可避免的。这种暴力解法的时间复杂度通常是 $O(n^2)$ ，在数据规模较大时，效率会变得非常低下。

双指针技术提供了一种优雅的替代方案。它巧妙地利用了问题的某些性质（如单调性），通过两个指针的协同移动，以线性的时间复杂度 $O(n)$ 完成任务。这种思想不仅能极大地提升算法性能，还能简化代码逻辑，是算法优化工具箱中不可或缺的一环。

问题定义

双指针并非一个特定的算法，而是一种算法思想，可以应用于多种问题模式。其共性在于：

给定一个序列（如数组、链表或字符串），使用两个指针（通常命名为 i 和 j，或 left 和 right）从序列的某个位置开始，根据一定的规则同步或异步移动，直到两个指针相遇或满足某个终止条件。在移动过程中，通过指针所指向的元素来更新状态或寻找答案。

一句话算法

通过维护两个指针在序列中的相对位置，将多重循环问题转化为单次遍历，实现线性时间复杂度的优化。

关键思路

双指针的核心在于 减少冗余计算。它通过指针的移动来“缩小”问题的搜索空间。根据指针的移动方向和初始位置，双指针主要分为两类：

相向双指针 (Opposite Direction Pointers):
- 初始位置: 一个指针在序列的开头，另一个在结尾。
- 移动方式: 两个指针向中间靠拢。
- 适用场景: 通常用于已排序的序列，利用单调性来寻找满足特定和、差或其它关系的目标对。
同向双指针 (Same Direction Pointers / Sliding Window):
- 初始位置: 两个指针通常都从序列的开头开始。
- 移动方式: 一个指针（快指针）先行探索，另一个指针（慢指针）在满足条件时跟进。它们共同维护一个“窗口”。
- 适用场景: 常用于寻找满足特定条件的连续子数组或子串，如“寻找最小的区间和”、“无重复字符的最长子串”等。

无论是哪种模式，关键都在于 正确地定义指针的移动策略。我们必须保证，在每一步移动后，我们都不会错过可能的解。

算法步骤与代码实现

我们将通过几个经典问题来具体展示双指针的应用。

指定和的整数对

问题定义: 在一个整数数组 nums 中，寻找两个数，使它们的和等于一个给定的目标值 target。返回这两个数的下标。

常用方法

二重暴力循环枚举
二分法
哈希表(桶)
双指针

双指针法

算法步骤:

先排序
初始化左指针 left = 0，右指针 right = n - 1（n 为数组长度）。
当 left < right 时，进行循环：
1. 计算当前指针指向的两个元素的和 current_sum = nums[left] + nums[right]。
2. 如果 current_sum == target，则找到了目标对，返回 left 和 right。
3. 如果 current_sum < target，说明和太小了。由于数组是排序的，需要增大和，因此将左指针向右移动 left++。
4. 如果 current_sum > target，说明和太大了。需要减小和，因此将右指针向左移动 right--。
如果循环结束仍未找到，则说明不存在这样的整数对。

复杂度分析:

时间复杂度: $O(n)$ 。两个指针最多各移动 n 次。
空间复杂度: $O(1)$ 。

证明思路

这里用到了单调性的性质,

[i ................... j]

初始的i,j: 答案必然在区间 $[i,j]$ 内
如果 $a[i] + a[j] < target$ ,那么 $a[i] + a[k] < target ( i< k < j)$ ,这说明 $a[i]$ 太小了,永远不可能是答案,那么可以把 $i$ 从答案区间里面删除,即i++,这样新的答案区间就变成了 $[i+1,j]$
如果 $a[i] + a[j] > target$ ,那么 $a[k] + a[j] < target \quad i< k < j$ ,这说明 $a[j]$ 太大了,永远不可能是答案,那么可以把 $j$ 从答案区间里面删除,即 $j--$ ,这样新的答案区间就变成了 $[i,j-1]$
显然,刚开始的区间 $[0,n-1]$ 是符合条件的,这样递归下去一定可以得到答案

问: 当 $a[i] + a[j] == target$ 的时候, $i,j$ 应该如何移动呢? 答: 思考方式和上面一样,这是 $i,j$ 都可以移动,可以 $i++$ 或 $j--$

代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

        // 在已排序数组中寻找和为 target 的两个数
void find_sum_pair(int nums[], int n,int target) {
    sort(nums,nums+n);
    int left = 0;
    int right = n - 1;

    while (left < right) {
        int current_sum = nums[left] + nums[right];
        if (current_sum == target) {
            // 找到目标对
            cout << left << " " << right << endl;
            i++; // 继续寻找下一对
        } else if (current_sum < target) {
            // 和太小，移动左指针
            left++;
        } else {
            // 和太大，移动右指针
            right--;
        }
    }
}

判断回文串(hdu 2029)

问题定义: 判断一个字符串是否是回文串（正读和反读都一样）。

算法步骤:

初始化左指针 left = 0，右指针 right = s.length() - 1。
当 left < right 时，进行循环： a. 比较 s[left] 和 s[right]。 b. 如果 s[left] != s[right]，则该字符串不是回文串，返回 false。 c. 如果相等，则继续向中间收缩指针：left++，right--。
如果循环正常结束，说明所有对称位置的字符都相等，返回 true。

复杂度分析:

时间复杂度: $O(n)$ 。
空间复杂度: $O(1)$ 。

证明

直觉的创建一个命题:

若 $A$ : $P(i,j)$ 表示字符串 $s[i..j]$ 是回文串
则 $B$ : $P(i,j) = P(i+1,j-1) \quad \text{且} \quad s[i] == s[j]$
一个命题和它的逆否命题等价: $A \to B \Leftrightarrow \neg B \to \neg A$

代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        #include <string>
#include <iostream>

bool is_palindrome(const string& s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

最多删除一个字符构成回文

给定一个字符串，最多删除一个字符,判断是否构成回文

这是一个经典的“双指针”算法题目（常见于 LeetCode 680. Valid Palindrome II）。

核心思路是：使用左右指针向中间逼近，当遇到不匹配的字符时，我们有一次“豁免权”来尝试删除左边或右边的字符。

算法逻辑

初始化：设置两个指针，left 指向字符串开头，right 指向字符串结尾。
循环比较：当 left < right 时：
- 如果 s[left] == s[right]：两个字符匹配，left 向右移，right 向左移，继续比较。
- 如果 s[left] != s[right]：发现不一致。此时我们有且仅有一次删除机会。我们需要验证以下两种情况中的任意一种是否成立：
  - 情况 A：假定删除左边的字符（s[left]），判断剩下的子串 s[left+1 ... right] 是否为回文。
  - 情况 B：假定删除右边的字符（s[right]），判断剩下的子串 s[left ... right-1] 是否为回文。
- 如果情况 A 或情况 B 任意一个为真，则返回 True；否则返回 False。
成功结束：如果循环走完没有遇到不匹配，说明原字符串本身就是回文，返回 True。

代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

        bool isPalindrome(const string& s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

bool validPalindrome(string s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        } else {
            // 遇到不匹配：
            // 1. 跳过左边字符 (检查 left+1 到 right)
            // 2. 跳过右边字符 (检查 left 到 right-1)
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }
    }
    return true;
}

复杂度分析

时间复杂度： $O(N)$ 。
- 最坏情况下，我们需要遍历整个字符串一次。
- 当遇到不匹配时，我们最多会额外调用两次 $O(N)$ 的子串检查，但总的操作次数仍然与字符串长度成线性关系。
空间复杂度： $O(1)$ 。
- 我们要只使用了几个变量（指针）来存储索引，不需要额外的数组或递归栈空间。

图解示例：`s = "abca"`

left=0 ('a'), right=3 ('a')。相等，left++ ,right--。
left=1 ('b'), right=2 ('c')。不相等！
进入分支判断：
- 尝试删左边 (left+1 到 right): 也就是判断索引 2 到 2 (“c”)。它是回文吗？是。 $\rightarrow$ 返回 True。
- (由于是逻辑或 OR 运算，此时无需再判断右边，直接得出结果)。

证明

这个方法是贪心. 使用交换验证的方法,证明两侧相同的字符是一定可以不删除.

若 $a[i] == a[j]$ ,如果删除 $a[j]$ 后,剩余的是回文,那么 $a[i] == a[j-1]$ ,那么显然可以不删除 $a[j]$ ,变成删除 $a[j-1]$ , 那么这个递归下去,相同的都可以不删除

证明核心抓住了回文串的一个本质特征：冗余性（Redundancy）。

命题：当 $a[i] == a[j]$ 时，最优解一定不需要删除这两个字符中的任何一个。

证明（基于你的交换/递归思路）：

假设：假设在 $a[i] == a[j]$ 的情况下，存在一个解法必须删除 $a[j]$ 才能构成回文。
推导：
- 既然删除了 $a[j]$ 后变成了回文，那么新的右边界 $a[j-1]$ 必须和左边界 $a[i]$ 相等（即 $a[i] == a[j-1]$ ）。
- 关键点：因为已知 $a[i] == a[j]$ ，且推导出 $a[i] == a[j-1]$ ，根据传递性，必然有 $a[j] == a[j-1]$ 。
交换（Exchange）：
- 既然 $a[j]$ 和 $a[j-1]$ 是一模一样的字符。
- 那么，“删除外层的 $a[j]$ ” 和 “保留外层的 $a[j]$ 但删除内层的 $a[j-1]$ ”，对于剩余的字符串结构来说，效果是完全等价的。
结论（递归/归纳）：
- 既然效果等价，我们为什么不保留那个外层的 $a[j]$ 呢？我们可以安全地把“删除操作”向内推迟给 $a[j-1]$ 。
- 如果 $a[j-1]$ 还和更里面的字符相同，我们可以继续向内推迟。
- 最终结论：只要字符相等，删除操作永远可以被“挤”到内部去，绝不需要在当前边界消耗掉。

这个证明好在两点：

更符合直觉（物理意义）：你证明了如果 $a[j]$ 和 $a[i]$ 相等，那么删 $a[j]$ 等同于删 $a[j-1]$ 。这就像是在说：“如果有两个一样的积木挨在一起，抽掉哪一个对整体结构的影响是一样的，所以我干嘛非要抽掉最外面那个支柱呢？”
揭示了本质（等效替代）：我的证明（资源论）侧重于“利益最大化”（有复活币比没复活币好），而你的证明侧重于“结构等效性”。你指出了在 $a[i]==a[j]$ 的情况下，删除边界是完全多余且可被替代的操作。

总结的金句：

“只要两侧相等，删除操作就可以无限向内推迟，直到遇到不等为止。”

寻找区间和

输出正整数数组里面所有满足条件： $Sum ( i,j ) == target$ 的区间

输入

15
6 1 2 3 4 6 4 2 8 9 10 11 12 13 14
6

输出

算法步骤:

初始化快指针 j = 0，慢指针 i = 0。
初始化当前窗口的和 sum = a [0]。
如果 sum == target, 输出一个解，然后 j++, sum += a [j]
如果 sum < target, j++, sum += a [j]
如果 sum > target, i++, sum -= a [i]

当 current_sum == target 时，说明当前窗口满足条件，此时为什么尝试不尝试的缩小左边界： $i++$ , 其实也可以，但是这个为了好看，保证 $j>=i$ , 所以这里放大右边界，即 $j++$

代码

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

        # include <bits/stdc++.h>
using namespace std;
int n;
int a [100009];
int m;

void findsum ( int a[],int n,int target ) {
  int i = 0,j = 0;
  int sum = a [0];
  while ( j < n ) {
    if ( sum == target ) {
      cout << i << " " << j << endl;
      j++; // 这里可能有越界 bug, 但是下一次循环会判断
      sum += a [j];
    }else if ( sum < target ) {
      j++; // 这里可能有越界 bug, 但是下一次循环会判断
      sum += a [j];
    }else{ // 移动 i
      sum -= a [i];
      i++;
    }
  }
}

int main ( ) {
    std:: cin >> n;
    for ( int i = 0;i < n ;++i ) // i: 0->n
    {
        std:: cin >> a [i];
    }
    std:: cin >> m;
    findsum ( a, n, m ) ;
    return 0;
}

注意：这种方法只适用于正整数数组，如果数组中有负数，那么就不可以了，因为破坏了单调性

证明

这里其实用到了区间和单调性 : $sum ( i,j ) < sum ( i,j+1 )$

只需要证明，如果存在一对 $( i_0,j_0 )$ , 使得 $sum ( i_0,j_0 ) == target$ , 那么算法不可能漏掉这对 $( i_0,j_0 )$ , 即证明了算法的 正确性.

分情况讨论，当 $j$ 到达 $j_0$ 的时候， $i$ 的位置

$i < i_0$ : 说明 $sum ( i,j )> target$ , 那么 $i$ 会一直向右移动，直到 $i == i_0$
$i == i_0$ : 说明 $sum ( i,j ) == target$ , 那么输出 $( i,j )$
$i > i_0$ : 证明当 j 到达 $j_0$ 的时候， $i$ 已经越过了 $i_0$ , 那么某个时刻 $i = i_0$ , 这个时候 k 一定小于 $j_0$ , 那么 $sum ( i,k ) < target$ , 那么 $i$ 不会向右移动，而是 $j$ 向右移动，直到 $j$ 到达 $j_0$ , 那么 $sum ( i,j ) == target$ , 那么输出 $( i,j )$ , 则 $i_0$ 不会被漏掉 ( 反证法 )

当然也可以认为这个过程是根据单调性对二重循环的优化 : 寻找以元 $a [j]$ 为结尾的满足条件的区间。

转换成前缀和

此时问题变成了，求有多少对元素满足： $P [j] - P [i] == target$

首先你可以写一个二重循环的暴力代码，枚举 $a [j]$ 为结尾的所有的可能的数对

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

        #include <iostream>
#include <utility>
using namespace std;
int n;
int m;

struct Node {
    int val,id;
    bool operator<(const Node &t)const {
        return val < t.val;
    }
};
Node p[100009];

void work(){
    for(int j = 1;j<=n;j++) {
        for(int i = 0 ;i<j;i++) {
            if( p[j].val - p[i].val == m)
            {
                int t1 = p[j].id;
                int t2 = p[i].id+1;
                if( t1 > t2) std::swap(t1, t2);
                cout << t1 << " " << t2 << endl;
            }
        }
    }
}

int main() {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 0->n
    {
        int t;
        std::cin >> t;
        p[i] = {p[i-1].val +t ,i};
    }
    std::cin >> m;
    sort(p,p+1+n); //排序
    work();
    return 0;
}

好的当你理解的暴力代码，那么你就可以理解下面，暴力优化, 利用排序后前缀和数组的单调性

$p [j] - p [i] = m$ , 就是所求
$p [j] - p [i] > m$ , 则对于所有的 $k <= i$ , $p [j] - p [k] > m$ , 那么 $[0,i]$ 就是相对于 $j$ 的失配区间，此时应该尝试 $i++$
如果 $[1,k]$ 是 $p [j]$ 失配区间，那么对于 $p [j+1]$ 也是失配区间
$p [j] - p [i] < m$ , 则区间 $k \in [i+1,j-1]$ , 都有 $p [j] - p [k] < m$ , 此时 $p [j]$ 已经尝试了所有的可能性，则 $j++$

注：使用前缀和法，可以在存在负值的数组上求满足条件的区间和

@include-code ( ./code/presum2.cpp, cpp )

对应的题目 luogu-P1102 A-B 数对 tags: [双指针]

寻找大于等于 target 的最短子数组和

问题定义: 给定一个正整数数组 nums 和一个目标值 target，找到数组中满足其和 ≥ target 的 连续子数组 的 最小长度。如果不存在，则返回 0。

6
2 3 1 2 4 3
7

算法步骤:

初始化快指针 j = 0，慢指针 i = 0。
初始化当前窗口的和 current_sum = 0，最小长度 min_len = infinity。
快指针 j 遍历整个数组，j 从 0 到 n-1：
1. 将 nums [j] 加入窗口，更新 current_sum += nums [j]。
2. 当 current_sum >= target 时，说明当前窗口满足条件，此时需要尝试收缩窗口的左边界：
  1. 更新最小长度 min_len = min ( min_len, j - i + 1 )。
  2. 将 nums [i] 移出窗口，current_sum -= nums [i]。
  3. 慢指针 i 向右移动 i++。
  4. 持续这个 while 循环，直到 current_sum < target，即窗口不再满足条件。
遍历结束后，如果 min_len 仍为 infinity，说明没有找到，返回 0，否则返回 min_len。

复杂度分析:

时间复杂度: $O ( n )$ 。虽然有嵌套循环，但每个元素最多被快指针 j 访问一次，被慢指针 i 访问一次。
空间复杂度: $O ( 1 )$ 。

代码实现(暴力):

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

        #include <bits/stdc++.h>
#include <climits>
using namespace std;

int n,m;
int p[100];
int ans = INT_MAX;

int range_sum(int l,int r) {
    return p[r] - p[l-1];
}


int main() {

    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> p[i];
        p[i] += p[i-1];
    }
    std::cin >> m;

    for(int j = 1;j <= n ;++j ) // 结尾j
    {
        for(int i = 1;i <= j ;++i ) // i: 1->j
        {
            int len = j-i+1;
            int sum = range_sum(i,j);
            if( sum >= m && len < ans)
            {
                // cout << i << " " << j << endl;
                ans = len;
            }
        }
    }
    cout << ans<<endl;
    return 0;
}

显然我们还是可以基于这个二重循环的暴力，根据区间和的单调性进行优化

若 Sum ( i,j )>= target, 则 Sum ( i-1,j )>=target, Sum ( i,j+1 )>= target
当固定 j 时候，我们不停的缩小 i 到达一个 Sum ( i,j ) < target 的时候
- $k \in [i,j]$ 所有的 $Sum ( k,j ) < target$ 这部分区间都不要考虑了，以 j 为为结尾的答案已经枚举玩了，现在要枚举 j+1 为结尾的
- 已知 $Sum ( i-1,j )>=target \Rightarrow Sum ( i-1,j+1 )>target$ , 且区间 $[i-1,j+1]$ 的长度比区间 $[i-1,j]$ 长
- 那么对于 j+1 结尾的枚举 i , 就应用从 i+1 开始
就这样递归下去

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

        #include <bits/stdc++.h>
#include <climits>
using namespace std;

int n,m;
int a[100];
int ans = INT_MAX;


int main() {

    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }
    std::cin >> m;

    int i = 1;
    int sum = 0;
    for(int j = 1;j <= n ;++j ) // 结尾j
    {
        sum += a[j];
        while( sum >= m) {
            ans = std::min(ans,j-i+1);
            sum -=a[i];
            i++;
        }
    }
    cout << (ans == INT_MAX ? 0 : ans) <<endl;
    return 0;
}

当然也可以转成前缀和来做: 转成求 $A-B >= C$ 的最小区间

对应的题目 poj-3061 Subsequence tags: [双指针]

经典例题

luogu-P1102 A-B 数对 tags: [双指针]
poj-3061 Subsequence tags: [双指针]
poj-2566 Bound Found tags: [双指针]
hdu-5358 First One tags: [双指针,log结果优化]
uva-11572 Unique Snowflakes tags: [双指针]
LeetCode 167. Two Sum II - Input array is sorted:
- 描述: 即“指定和的整数对”问题。
- 思路: 使用相向双指针。
LeetCode 209. Minimum Size Subarray Sum:
- 描述: 即“寻找大于等于 target 的最短子数组和”问题。
- 思路: 使用同向双指针（滑动窗口）。
LeetCode 11. Container With Most Water:
- 描述: 给定一个非负整数数组，每个数代表一个坐标点上的垂直线的高度。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
- 思路: 这是一个经典的相向双指针问题。
  - 初始化 left=0, right=n-1。
  - 计算当前容器面积 area = min(height[left], height[right]) * (right - left)。
  - 关键在于移动策略：为了尽可能找到更大的面积，我们应该移动 高度较短 的那条边的指针。因为容器的宽度 (right - left) 在不断减小，只有通过移动短板，才 有可能 找到一个更高的板来弥补宽度的损失，从而得到更大的面积。如果移动长板，面积必然不会增大。

实践思考与扩展

三指针问题: 双指针的思想可以扩展到三个甚至更多指针，用于解决更复杂的问题，如“三数之和”。
链表中的双指针: 双指针在链表中也有广泛应用，如“快慢指针”判断链表是否有环、寻找链表中点、删除倒数第 N 个节点等。
与二分查找的关系: 对于某些问题，双指针和二分查找可以互相替代。例如，在有序数组中寻找和为 target 的数对，也可以通过遍历每个数 x，然后二分查找 target - x 来解决，但时间复杂度为 $O(n \log n)$ ，不如双指针的 $O(n)$ 高效。

目录

摘要

背景与动机

问题定义

一句话算法

关键思路

算法步骤与代码实现

指定和的整数对

常用方法

双指针法

证明思路

代码实现

判断回文串(hdu 2029)

证明

代码实现

最多删除一个字符构成回文

算法逻辑

代码实现

复杂度分析

图解示例：s = "abca"

证明

寻找区间和

算法步骤:

证明

转换成前缀和

寻找大于等于 target 的最短子数组和

经典例题

实践思考与扩展

图解示例：`s = "abca"`