双指针算法：优雅地优化循环

摘要

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

背景与动机

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

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

问题定义

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

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

一句话算法

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

关键思路

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

1. 相向双指针 (Opposite Direction Pointers):

   • 初始位置: 一个指针在序列的开头，另一个在结尾。
   • 移动方式: 两个指针向中间靠拢。
   • 适用场景: 通常用于已排序的序列，利用单调性来寻找满足特定和、差或其它关系的目标对。

2. 同向双指针 (Same Direction Pointers / Sliding Window):

   • 初始位置: 两个指针通常都从序列的开头开始。
   • 移动方式: 一个指针（快指针）先行探索，另一个指针（慢指针）在满足条件时跟进。它们共同维护一个“窗口”。
   • 适用场景: 常用于寻找满足特定条件的连续子数组或子串，如“寻找最小的区间和”、“无重复字符的最长子串”等。

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

算法步骤与代码实现

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

指定和的整数对

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

常用方法

1. 二重暴力循环枚举
2. 二分法
3. 哈希表(桶)
4. 双指针

双指针法

算法步骤:

1. 先排序
2. 初始化左指针 left = 0，右指针 right = n - 1（n 为数组长度）。
3. 当 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--。
4. 如果循环结束仍未找到，则说明不存在这样的整数对。

复杂度分析:

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

证明思路

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

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

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

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

代码实现

        
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--;
        }
    }
}

    

对应题目 luogu-T609340 找指定和的整数对 tags: [双指针,二分] : 详细论证了暴力到双指针的进化

判断回文串(hdu 2029)

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

算法步骤:

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

代码实现

        
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）。

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

算法逻辑

1. 初始化：设置两个指针，left 指向字符串开头，right 指向字符串结尾。
2. 循环比较：当 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。
3. 成功结束：如果循环走完没有遇到不匹配，说明原字符串本身就是回文，返回 True。

代码实现

        
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"

1. left=0 ('a'), right=3 ('a')。相等，left++ ,right--。
2. left=1 ('b'), right=2 ('c')。不相等！
3. 进入分支判断：
   • 尝试删左边 (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]$ 时，最优解一定不需要删除这两个字符中的任何一个。

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

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

这个证明好在两点：

1. 更符合直觉（物理意义）： 你证明了如果 $a[j]$ 和 $a[i]$ 相等，那么删 $a[j]$ 等同于删 $a[j-1]$。这就像是在说：“如果有两个一样的积木挨在一起，抽掉哪一个对整体结构的影响是一样的，所以我干嘛非要抽掉最外面那个支柱呢？”

2. 揭示了本质（等效替代）： 我的证明（资源论）侧重于“利益最大化”（有复活币比没复活币好），而你的证明侧重于“结构等效性”。你指出了在 $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

输出

1 1
2 4
6 6
7 8

算法步骤:

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

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

代码

        
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$的位置

1. $i < i_0$ : 说明$sum ( i,j )> target$, 那么$i$会一直向右移动，直到$i == i_0$
2. $i == i_0$ : 说明$sum ( i,j ) == target$, 那么输出$( i,j )$
3. $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]$为结尾的所有的可能的数对

        
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;
}

    

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

1. $p [j] - p [i] = m$, 就是所求
2. $p [j] - p [i] > m$, 则对于所有的$k <= i$,$p [j] - p [k] > m$, 那么$[0,i]$就是相对于$j$的失配区间，此时应该尝试$i++$
3. 如果$[1,k]$是$p [j]$失配区间，那么对于$p [j+1]$也是失配区间
4. $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

2

算法步骤:

1. 初始化快指针 j = 0，慢指针 i = 0。
2. 初始化当前窗口的和 current_sum = 0，最小长度 min_len = infinity。
3. 快指针 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，即窗口不再满足条件。
4. 遍历结束后，如果 min_len 仍为 infinity，说明没有找到，返回 0，否则返回 min_len。

复杂度分析:

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

代码实现(暴力):

        
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 开始
• 就这样递归下去

        
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: [双指针]

A-B=C 的数对

给一个数组,和数字$C$,求数组中$A-B=C$的对数

• 暴力: $n^2$
• 二分
  1. 排序后不影响结果,先排序
  2. 固定一个数$A$,然后二分查找$B = A - C$的数量
  3. $O(nlogn)$

在一个不没有重复元素的数组中,求数组中$A-B=C$的对数

这是一个经典的**“同向双指针”**（Same-direction Two Pointers）问题。

与“两数之和”（Two Sum）不同，“两数之和”通常指针分别在头尾向中间靠拢；而“两数之差”需要两个指针都从左边出发，向右移动。

核心思路

1. 排序： 双指针法依赖于数据的单调性。原数组无序时，我们无法判断指针该往哪边移。 首先将数组从小到大排序。

2. 指针定义：

   • left 指针指向 $B$（较小的数）。
   • right 指针指向 $A$（较大的数）。
   • 我们要寻找满足 nums[right] - nums[left] == C 的情况。

3. 移动策略： 计算当前差值 diff = nums[right] - nums[left]：

   • 如果 diff < C：说明差太小了。因为 left 已经是最小能取的了，我们必须让被减数 $A$ 变大，所以 right 向右移。
   • 如果 diff > C：说明差太大了。我们要让减数 $B$ 变大（从而减小差值），所以 left 向右移。
   • 如果 diff == C：找到了！计数器 count++。
     • 由于题目保证没有重复元素，这对 $(A, B)$ 组合是唯一的。
     • 我们可以同时移动 left++ 和 right++ 来寻找下一对。

4. 特殊处理：

   • 如果 $C < 0$：由于题目求 $A-B=C$，即 $B-A = -C$。对数是一样的，取 $C = |C|$ 处理即可。
   • 为了避免 left 和 right 指向同一个元素（差为0，但题目通常隐含 $A, B$ 是不同元素，且若 $C>0$ 则不可能相同），通常初始化 right = 1 或者在循环中保证 right > left。

C++ 实现

        
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

        #include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

int countDiffPairs(vector<int>& nums, int c) {
    c = abs(c); // 统一转为正数处理
    sort(nums.begin(), nums.end()); // 1. 排序 O(N log N)
    
    int n = nums.size();
    int left = 0;
    int right = 1;
    int count = 0;
    
    while (right < n) {
        if (left == right) {
            right++;
            continue;
        }
        
        long long diff = (long long)nums[right] - nums[left];
        
        if (diff == c) {
            count++;
            left++;
            right++; // 无重复元素，可以大胆同时移
        } else if (diff < c) {
            right++; // 差小了，变大 A
        } else {
            left++;  // 差大了，变大 B
        }
    }
    
    return count;
}

    

复杂度分析

1. 时间复杂度: $O(N \log N)$

   • 排序 消耗 $O(N \log N)$。
   • 双指针遍历 消耗 $O(N)$。因为 left 和 right 都只会从头走到尾，互不回头。
   • 总复杂度由排序主导。

2. 空间复杂度: $O(1)$ (不计算存储输入输出的空间，仅看额外变量)。

   • 如果是 Python 的 sort (Timsort) 可能需要 $O(N)$ 的栈空间。C++ std::sort 通常是 $O(\log N)$。

对比：如果有重复元素怎么办？

如果题目去掉了“无重复元素”的条件（例如 [1, 1, 4, 4], $C=3$），代码会变得麻烦：

• 当 diff == C 时，我们不能简单地 left++, right++。
• 我们需要计算 left 指向的数字有几个（比如 $x$ 个），right 指向的数字有几个（比如 $y$ 个）。
• 这一轮的贡献是 $x \times y$。
• 然后指针跳过所有相同的元素。
• 本题因为“无重复”这一条件，极大地简化了逻辑。

证明

为了证明这个双指针算法的正确性，我们利用**“单调性”和“解空间覆盖”**的思路。

我们要证明的核心是：算法绝对不会错过任何一对满足条件的 $(A, B)$。

假设数组 $Nums$ 已经升序排列，目标对是 $(i, j)$，即 $Nums[j] - Nums[i] = C$ （其中 $i < j$）。

证明思路：反证法 (Proof by Contradiction)

我们假设存在一对标准答案 $(i, j)$，但是算法运行结束时没有找到它。

分析算法流程： 右指针 $R$ 从左向右一步步走，必然会在某个时刻到达位置 $j$。 我们要观察：当 $R$ 刚刚到达 $j$ 这一瞬间，左指针 $L$ 在哪里？

只有三种情况：

情况 1：$L$ 还在 $i$ 的左边 ($L < i$)

• 现状：$R = j$, $L < i$。
• 推导： 由于数组单调递增，$L < i \implies Nums[L] < Nums[i]$。 计算差值：$Diff = Nums[j] - Nums[L]$。 因为 $Nums[L]$ 比标准答案 $Nums[i]$ 小，所以 $Diff$ 必定大于 $C$。
• 算法行为：根据算法逻辑，当 Diff > C 时，执行 L++。
• 结果：$L$ 会一直向右移动，直到 $L$ 变成 $i$。此时 $Diff$ 变成 $C$，答案被找到。
• 结论：如果 $L$ 落后了，它会被强制追上来，不会漏。

情况 2：$L$ 正好在 $i$ 的位置 ($L = i$)

• 现状：$R = j$, $L = i$。
• 推导：$Diff = Nums[j] - Nums[i] = C$。
• 结果：直接命中，计数 count++。
• 结论：没有漏。

情况 3：$L$ 已经跑到了 $i$ 的右边 ($L > i$) —— 这是唯一需要反驳的“漏网之鱼”情况

• 假设：当 $R$ 刚走到 $j$ 时，$L$ 却早已越过了 $i$。
• 回溯推理：
  • $L$ 要越过 $i$（从 $i$ 变成 $i+1$），必然是在之前的某个时刻发生的。
  • 让时间倒流回 $L$ 停留在 $i$ 的那个时刻。
  • 在那一刻，右指针 $R$ 一定在 $j$ 的左边某个位置，设为 $k$ ($k < j$)。
  • 当时为何 $L$ 会移动？ 算法规定只有当 Nums[R] - Nums[L] > C 时，$L$ 才会右移。
  • 所以，当时必然满足：$Nums[k] - Nums[i] > C$。
• 寻找矛盾：
  • 已知 $k < j$ (右指针还没走到 $j$)，根据数组升序，则 $Nums[k] < Nums[j]$。
  • 那么：$Nums[k] - Nums[i] \quad < \quad Nums[j] - Nums[i]$。
  • 我们已知 $Nums[j] - Nums[i] = C$。
  • 所以推出：$Nums[k] - Nums[i] < C$。
• 矛盾点：
  • 算法逻辑要求：只有差值 大于 $C$ 才会移走 $L$。
  • 数学事实推导：此时差值 小于 $C$。
  • 结论：在 $R$ 到达 $j$ 之前，$L$ 绝对不可能因为差值过大而提前移过 $i$。

总结

1. 右指针负责地毯式搜索，一定会经过 $j$。
2. 左指针受到数学逻辑的严格约束：
   • 只要 $R$ 还没到 $j$，差值就不够大，$L$ 就不敢越过 $i$。
   • 一旦 $R$ 到了 $j$，如果 $L$ 还在后面，差值就太大，$L$ 被迫赶去 $i$。
3. 因此，两个指针必在 $(i, j)$ 处相遇。

这个证明展示了算法的严谨性，确保了它不会漏掉任何一对满足条件的 $(A, B)$。

拓展

问题更改: 求满足 $k1 <=A-B <= k2$ 的对数

思路一样,但这里使用三指针

先排序,固定前一个指针$a[i]$

找到第一个$k1 \leqslant a[j_1] - a[i]$,因为单调性,$j_1$右移增加,那么 $a[j_1] - a[i]$ 就会增加,直到到达边界 $k2$,此时$j_2$

显然 $i \to i+1$ 的时候,$j_1,j_2$ 增加.

暴力代码

        
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

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

int n;
int a[10000];
int k1,k2;

int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }
    std::cin >> k1 >> k2;
    std::sort(a+1,a+1+n);

    int ans = 0;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j = i;j <= n ;++j ) // j: 1->n
        {
            int t = a[j] - a[i];
            if( t >= k1 && t <= k2)
                ans++;
        }
    }
    std::cout << ans << "\n";
    return 0;
}

    

优化代码

        
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

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

int n;
int a[10000];
int k1,k2;

int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }
    std::cin >> k1 >> k2;
    std::sort(a+1,a+1+n);

    int cnt=0;
    int j1 =1 ,j2 = 1;
    for(int i = 1;i <= n;i++) {
        // 找到第一满足 >= k1条件的j1
        // 第一个不满足 < k1 条件的j1
        while( a[j1] - a[i] < k1  && j1 <=n ) j1++;

        // 找到最后一个满足条件的j2
        // 前一个位置 j2-1 就是最后一个满足 <= k2 位置
        while( a[j2] - a[i] <= k2 && j2 <=n ) j2++;
        if( j1 <= n  && j2 >= j1 ) {
            // ? (j2-1)-j1 + 1 = j2-j1
            // [j1,j2) 就是满足的区间
            cnt += ( j2 - j1);
        }
    }
    std::cout << cnt << "\n";
    return 0;
}

    

经典例题

1. luogu-P1102 A-B 数对 tags: [双指针,二分]

2. poj-3061 Subsequence tags: [双指针]

3. poj-2566 Bound Found tags: [双指针]

4. hdu-5358 First One tags: [双指针,log结果优化]

5. uva-11572 Unique Snowflakes tags: [双指针]

6. LeetCode 167. Two Sum II - Input array is sorted:

   • 描述: 即“指定和的整数对”问题。
   • 思路: 使用相向双指针。

7. LeetCode 209. Minimum Size Subarray Sum:

   • 描述: 即“寻找大于等于 target 的最短子数组和”问题。
   • 思路: 使用同向双指针（滑动窗口）。

8. 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)$ 高效。