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

摘要

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

背景与动机

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

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

问题定义

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

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

一句话算法

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

关键思路

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

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

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

算法步骤与代码实现

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

id: base-double-point-1 title: 指定和的整数对 description: 使用相向双指针在有序数组中寻找两数之和等于目标值，利用单调性将暴力 O(n²) 优化到 O(n)。 tags: [“双指针”, “两数之和”, “基础算法”]

指定和的整数对

问题定义: 在一个整数数组 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

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

        // 在已排序数组中寻找和为 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 : 详细论证了暴力到双指针的进化

id: base-double-point title: 判断回文串 description: 使用相向双指针判断字符串是否为回文串，O(n) 时间、O(1) 空间。 tags: [“双指针”, “回文串”, “基础算法”]

判断回文串(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

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

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

id: base-double-point-3 title: 最多删除一个字符构成回文 description: 最多删除一个字符判断能否构成回文串，双指针配合贪心交换论证实现 O(n) 判定。 tags: [“双指针”, “回文串”, “贪心”, “基础算法”]

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

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

这是一个经典的“双指针”算法题目（常见于 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

        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

        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]$ 的情况下，删除边界是完全多余且可被替代的操作。

总结的金句：

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

id: “double-pointer-range-sum” title: “双指针寻找区间和” description: 双指针寻找区间和的原理与实现：利用正整数数组的单调性，用左右指针维护窗口实现 O(n) 查找。 date: 2026-06-16 21:10 toc: true tags: [“双指针”, “滑动窗口”, “前缀和”] categories: [“基础算法”]

一句话算法

正整数区间和越扩越大、越缩越小，所以可以用左右指针维护一个窗口，让每个端点只走一遍。

问题模型

给定一个正整数数组 $a_1,a_2,\dots,a_n$ 和目标值 target，常见问题有两类：

输出所有满足区间和等于 target 的连续区间。
求区间和至少为 target 的最短连续区间长度。

这里的关键条件是：数组元素都是正整数。

如果数组里有负数，右端点右移不一定让区间和变大，左端点右移也不一定让区间和变小，滑动窗口的单调性会失效。

核心直觉

窗口 [left,right] 表示当前考虑的连续区间。

因为每个数都是正的：

right 向右移动，窗口和只会变大。
left 向右移动，窗口和只会变小。

所以当窗口和太小时，只能扩右端点；当窗口和太大或已经满足条件时，可以缩左端点。两个指针都只向右走，总复杂度就是线性的。

算法步骤

输出所有和等于 target 的区间

初始化 left = 1，sum = 0。
枚举右端点 right = 1..n：
- 把 a[right] 加入 sum。
- 当 sum > target 时，不断移出 a[left] 并右移 left。
- 如果 sum == target，输出 [left,right]。

求和至少为 target 的最短区间

初始化 left = 1，sum = 0，ans = n+1。
枚举右端点 right = 1..n：
- 把 a[right] 加入 sum。
- 当 sum >= target 时：
  - 用当前长度更新答案。
  - 移出 a[left]，右移 left，尝试缩短区间。
如果答案仍为 n+1，输出 0。

算法证明

关键不变量： 对每个右端点 right，左指针只会停在仍可能产生答案的位置，不会漏掉应该检查的左端点。

以“和等于 target”为例：

如果当前 sum > target，由于数组全为正数，继续扩大右端点只会让和更大。
因此当前左端点已经不可能和当前或更大的右端点形成答案，必须右移 left。
如果 sum < target，右移 left 只会让和更小，不可能得到答案，只能扩大 right。
任意答案区间 [L,R] 在右端点走到 R 时，左端点不会提前越过 L：在越过之前，窗口和不会因为正数单调性而被迫过度收缩。

所以每个合法区间都会在它的右端点被枚举到时被发现。

“至少为 target 的最短区间”同理：当窗口已经满足条件时，只有继续收缩左端点才可能得到更短答案；当窗口不满足时，只有扩大右端点才可能重新满足。

复杂度分析

两个指针都只从左到右移动一次。

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

前缀和排序版本需要排序：

时间复杂度： $O(n\log n)$ 。
空间复杂度： $O(n)$ 。

代码实现

正整数区间和等于 target

cpp

        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;

// Print all 1-indexed intervals whose sum is exactly target.
// The array must contain positive integers.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> target;

    int left = 1;
    long long sum = 0;

    for (int right = 1; right <= n; ++right) {
        sum += a[right];

        while (left <= right && sum > target) {
            sum -= a[left];
            ++left;
        }

        if (sum == target) {
            cout << left << ' ' << right << '\n';
        }
    }

    return 0;
}

前缀和暴力对照

cpp

        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
43
44
45

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

struct Prefix {
    long long value;
    int id;

    bool operator<(const Prefix& other) const {
        if (value != other.value) return value < other.value;
        return id < other.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<Prefix> prefix(n + 1);
    prefix[0] = {0, 0};

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = {prefix[i - 1].value + x, i};
    }
    cin >> target;

    sort(prefix.begin(), prefix.end());

    for (int j = 1; j <= n; ++j) {
        for (int i = 0; i < j; ++i) {
            if (prefix[j].value - prefix[i].value == target) {
                int l = min(prefix[i].id, prefix[j].id) + 1;
                int r = max(prefix[i].id, prefix[j].id);
                cout << l << ' ' << r << '\n';
            }
        }
    }

    return 0;
}

前缀和排序双指针

cpp

        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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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

struct Prefix {
    long long value;
    int id;

    bool operator<(const Prefix& other) const {
        if (value != other.value) return value < other.value;
        return id < other.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<Prefix> prefix(n + 1);
    prefix[0] = {0, 0};

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = {prefix[i - 1].value + x, i};
    }
    cin >> target;

    sort(prefix.begin(), prefix.end());

    vector<pair<int, int>> groups;
    for (int i = 0; i <= n;) {
        int j = i + 1;
        while (j <= n && prefix[j].value == prefix[i].value) ++j;
        groups.push_back({i, j});
        i = j;
    }

    if (target == 0) {
        for (auto [l, r] : groups) {
            for (int i = l; i < r; ++i) {
                for (int j = i + 1; j < r; ++j) {
                    int left = min(prefix[i].id, prefix[j].id) + 1;
                    int right = max(prefix[i].id, prefix[j].id);
                    cout << left << ' ' << right << '\n';
                }
            }
        }
        return 0;
    }

    int right_group = 0;
    for (int left_group = 0; left_group < (int)groups.size(); ++left_group) {
        right_group = max(right_group, left_group + 1);
        while (right_group < (int)groups.size()) {
            long long diff = prefix[groups[right_group].first].value
                           - prefix[groups[left_group].first].value;
            if (diff >= target) break;
            ++right_group;
        }
        if (right_group == (int)groups.size()) break;

        long long diff = prefix[groups[right_group].first].value
                       - prefix[groups[left_group].first].value;
        if (diff != target) continue;

        auto [l1, r1] = groups[left_group];
        auto [l2, r2] = groups[right_group];
        for (int i = l1; i < r1; ++i) {
            for (int j = l2; j < r2; ++j) {
                int left = min(prefix[i].id, prefix[j].id) + 1;
                int right = max(prefix[i].id, prefix[j].id);
                cout << left << ' ' << right << '\n';
            }
        }
    }

    return 0;
}

这份模板把相同前缀和值合成一组。target > 0 时在不同组之间做双指针；target == 0 时在同一组内两两配对。

最短和至少为 target 的子数组

暴力对照：

cpp

        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>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    cin >> target;

    int ans = n + 1;
    for (int left = 1; left <= n; ++left) {
        for (int right = left; right <= n; ++right) {
            long long sum = prefix[right] - prefix[left - 1];
            if (sum >= target) {
                ans = min(ans, right - left + 1);
                break;
            }
        }
    }

    cout << (ans == n + 1 ? 0 : ans) << '\n';
    return 0;
}

双指针优化：

cpp

        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>
using namespace std;

// Minimum length of a contiguous subarray with sum >= target.
// The array must contain positive integers.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> target;

    int ans = n + 1;
    int left = 1;
    long long sum = 0;

    for (int right = 1; right <= n; ++right) {
        sum += a[right];
        while (left <= right && sum >= target) {
            ans = min(ans, right - left + 1);
            sum -= a[left];
            ++left;
        }
    }

    cout << (ans == n + 1 ? 0 : ans) << '\n';
    return 0;
}

测试用例

寻找和等于 6 的区间：

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

输出：

寻找和至少为 7 的最短区间：

6
2 3 1 2 4 3
7

输出：

应用分类详解

区间和双指针的本质是“窗口状态对左右端点具有单调性”。

一、正整数区间和恰好为目标值

典型模式： 全是正整数，要求找连续子数组和等于某个值。 识别信号： 题面强调正整数或非负数；要求连续区间。 核心建模： 和太小扩右端点，和太大缩左端点。

应用场景	经典题目	核心思路
输出所有目标和区间	本文模型	双指针维护当前窗口和
尺取法基础题	poj-3061	正整数保证窗口单调

二、最短满足区间

典型模式： 找最短/最长连续区间，并且条件随窗口扩大单调变化。 识别信号： “最短子数组”“和至少为”“覆盖所有字符”等。 核心建模： 满足条件后尽量收缩左端点。

应用场景	经典题目	核心思路
最短和至少为 S	poj-3061	满足后缩左端点更新最短长度
最小覆盖子串	LeetCode 76	窗口满足覆盖条件后收缩

三、有负数时改用前缀和

典型模式： 数组可能含负数，窗口和不再单调。 识别信号： 数据范围允许负数，但仍然问区间和。 核心建模： 把区间和转成两个前缀和之差，再用排序、哈希表或平衡树处理。

应用场景	经典题目	核心思路
区间和等于 K	LeetCode 560	哈希表统计历史前缀和
接近目标的区间和	poj-2566	排序前缀和，双指针或邻近扫描

经典例题

poj-3061 正整数数组中求和至少为目标值的最短子数组，是滑动窗口的标准题。
poj-2566 数组允许负数，需要转成前缀和后处理。
LeetCode 209 和 POJ 3061 同模型，适合练习边界写法。

id: “diff-pair-count” title: “A-B=C 数对” description: 排序后双指针统计差值在指定范围内的数对数量，利用单调性 O(n) 扫描。 date: 2026-06-16 21:20 toc: true tags: [“双指针”, “数对统计”, “排序”] categories: [“基础算法”]

一句话算法

排序后固定小的数，满足差值下界和上界的右端点都会向右单调移动。

问题模型

给定数组 $a_1,a_2,\dots,a_n$ 和两个整数 low、high，统计满足：

low \le a_j-a_i \le high,\quad i<j

的数对数量。

当 low = high = C 时，就是常见的 A-B=C 数对问题。

核心直觉

先把数组排序。固定左端点 i 后，随着右端点 j 向右移动：

a_j-a_i

只会变大。

因此对每个 i：

第一个满足 a[j]-a[i] >= low 的位置记为 first_ge_low。
第一个满足 a[j]-a[i] > high 的位置记为 first_gt_high。

那么合法右端点就是半开区间：

[first_ge_low, first_gt_high)

贡献为：

first\_gt\_high-first\_ge\_low

当 i 右移时，这两个指针不会向左退。

算法步骤

将数组排序。
初始化两个右指针：
- first_ge_low = 1
- first_gt_high = 1
枚举左端点 i = 0..n-1：
- 保证两个右指针至少为 i+1，避免选同一个元素。
- 移动 first_ge_low，直到差值不小于 low。
- 移动 first_gt_high，直到差值大于 high。
- 当前 i 的贡献为 first_gt_high - first_ge_low。
输出贡献总和。

算法证明

关键不变量： 对固定的 i，[first_ge_low, first_gt_high) 正好是所有合法右端点。

排序后，函数 f(j)=a[j]-a[i] 随 j 单调不降。
所有 f(j)<low 的位置一定在左侧，移动 first_ge_low 后，它前面都不合法。
所有 f(j)<=high 的位置一定在 first_gt_high 左侧，移动后它及右侧都不合法。
因此两个边界之间的位置恰好满足 low <= f(j) <= high。
当 i 变大时，两个边界不会需要向左回退；即使差值变小，也从当前指针继续向右寻找，不会遗漏，因为更靠左的位置已经不满足 j>i 或已经被之前左端点分类处理。

每个合法数对都有唯一左端点 i，所以按 i 累加不重不漏。

复杂度分析

排序： $O(n\log n)$ 。
双指针扫描： $O(n)$ 。
总时间复杂度： $O(n\log n)$ 。
额外空间复杂度： $O(1)$ ，不计排序栈和输入数组。

暴力二重循环为 $O(n^2)$ 。

代码实现

暴力对照

cpp

        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

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

// Count pairs (i, j), i < j, whose sorted value difference is in [low, high].
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long low, high;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> low >> high;

    sort(a.begin(), a.end());

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long diff = a[j] - a[i];
            if (low <= diff && diff <= high) ++ans;
        }
    }

    cout << ans << '\n';
    return 0;
}

双指针优化

cpp

        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>
using namespace std;

// Count pairs (i, j), i < j, whose sorted value difference is in [low, high].
// Duplicates are counted by index pairs.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long low, high;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> low >> high;

    sort(a.begin(), a.end());

    long long ans = 0;
    int first_ge_low = 1;
    int first_gt_high = 1;

    for (int i = 0; i < n; ++i) {
        first_ge_low = max(first_ge_low, i + 1);
        first_gt_high = max(first_gt_high, i + 1);

        while (first_ge_low < n && a[first_ge_low] - a[i] < low) {
            ++first_ge_low;
        }
        while (first_gt_high < n && a[first_gt_high] - a[i] <= high) {
            ++first_gt_high;
        }

        ans += first_gt_high - first_ge_low;
    }

    cout << ans << '\n';
    return 0;
}

测试用例

输入：

6
1 5 3 4 2 8
2 3

输出：

排序后为 1 2 3 4 5 8。差值在 [2,3] 的下标对共有 6 个。

如果要统计 A-B=C，把 low 和 high 都设为 C。

应用分类详解

差值数对的本质是“排序后固定一端，另一端的合法范围是连续区间”。

一、固定差值数对

典型模式： 统计满足 $A-B=C$ 的数对。 识别信号： 题面出现“两数之差为 C”“差值等于 K”。 核心建模： 令 low=high=C，对每个左端点统计合法右端点个数。

应用场景	经典题目	核心思路
A-B=C	luogu-P1102	排序后二分或双指针统计差值为 C 的数对

二、差值范围数对

典型模式： 统计差值落在一个区间 [L,R] 内的数对。 识别信号： 题面问“距离不小于/不大于”“差值在范围内”。 核心建模： 两个右指针分别维护下界和上界。

应用场景	经典题目	核心思路
距离范围统计	本文模型	半开区间 `[first_ge_low, first_gt_high)` 给出贡献
接近目标的数对	双指针基础题	用有序性排除一整段无效候选

三、配合二分查找

典型模式： 对每个固定端点，用 lower_bound 和 upper_bound 统计另一个端点数量。 识别信号： 写双指针不方便，但数据已排序。 核心建模： lower_bound(a+i+1, low+a[i]) 找下界，upper_bound(a+i+1, high+a[i]) 找上界。

应用场景	经典题目	核心思路
固定差值计数	luogu-P1102	每个 `A` 二分查 `A-C` 或每个 `B` 查 `B+C`

经典例题

luogu-P1102 A-B=C 模板题。注意重复元素要按下标对计数。
本文差值范围模型适合练习两个边界指针如何分别维护下界和上界。
Two Sum II 与差值数对类似，都是排序后利用单调性移动指针。

经典例题

luogu-P1102
poj-3061
poj-2566
hdu-5358
uva-11572
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)$ 高效。

摘要

背景与动机

问题定义

一句话算法

关键思路

算法步骤与代码实现

id: base-double-point-1 title: 指定和的整数对 description: 使用相向双指针在有序数组中寻找两数之和等于目标值，利用单调性将暴力 O(n²) 优化到 O(n)。 tags: [“双指针”, “两数之和”, “基础算法”]

指定和的整数对

常用方法

双指针法

证明思路

代码实现

对应题目 luogu-T609340 : 详细论证了暴力到双指针的进化

id: base-double-point title: 判断回文串 description: 使用相向双指针判断字符串是否为回文串，O(n) 时间、O(1) 空间。 tags: [“双指针”, “回文串”, “基础算法”]

判断回文串(hdu 2029)

证明

代码实现

id: base-double-point-3 title: 最多删除一个字符构成回文 description: 最多删除一个字符判断能否构成回文串，双指针配合贪心交换论证实现 O(n) 判定。 tags: [“双指针”, “回文串”, “贪心”, “基础算法”]

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

算法逻辑

代码实现

复杂度分析

图解示例：s = "abca"

证明

一句话算法

问题模型

核心直觉

算法步骤

输出所有和等于 target 的区间

求和至少为 target 的最短区间

算法证明

复杂度分析

代码实现

正整数区间和等于 target

前缀和暴力对照

前缀和排序双指针

最短和至少为 target 的子数组

测试用例

应用分类详解

一、正整数区间和恰好为目标值

二、最短满足区间

三、有负数时改用前缀和

经典例题

id: “diff-pair-count” title: “A-B=C 数对” description: 排序后双指针统计差值在指定范围内的数对数量，利用单调性 O(n) 扫描。 date: 2026-06-16 21:20 toc: true tags: [“双指针”, “数对统计”, “排序”] categories: [“基础算法”]

一句话算法

问题模型

核心直觉

算法步骤

算法证明

复杂度分析

代码实现

暴力对照

双指针优化

测试用例

应用分类详解

一、固定差值数对

二、差值范围数对

三、配合二分查找

经典例题

经典例题

实践思考与扩展

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