双指针：原理、图解与 C++ 实战

一、什么是双指针

双指针（Two Pointers）是指在遍历数据结构时使用两个指针变量协同移动的一种技巧。两个指针按特定规则前进，从而避免暴力枚举所有组合，把原本 O(n²) 的双重循环优化到 O(n)。

双指针并不是一种具体的算法，而是一类思想的总称。根据两个指针的运动方向不同，主要分三种形态：

1.1 三种主要形态

双指针之所以高效，核心是"单调性剪枝"：当某对 (i, j) 不满足条件时，我们能根据单调性直接排除掉一整片不可能的组合，而不需要逐一尝试。

二、核心原理与图解

理解双指针的关键，是理解"为什么指针只往一个方向走，不会错过答案"。下面分别用三张图展示对撞、快慢、滑动三种典型过程。

2.1 对撞指针过程图

以有序数组 [2, 3, 4, 6, 8, 11, 15] 找和为 15 的两数为例。两个指针 left、right 分别从两端出发，根据 nums[left] + nums[right] 与目标的大小关系决定移动哪一侧。

2.2 快慢指针过程图

快慢指针多用于链表。两个指针同时从头出发，快指针一次走两步，慢指针一次走一步。当快指针到达末尾时，慢指针恰好在链表中点。

2.3 左右指针滑动过程图

左右指针同向而行：右指针 right 主动右扩，左指针 left 在窗口不满足条件时右缩。下面以"和 ≥ 7 的最短子数组"演示这一过程。

2.4 复杂度分析

三、通用模板

双指针没有"一种模板吃所有题"的统一写法，但对撞和快慢各有典型骨架。下面给出两种最常见的模板。

3.1 对撞指针模板

// 对撞指针通用模板：在有序数组中找满足条件的两数
vector<int> twoSumSorted(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};   // 命中
        } else if (sum < target) {
            ++left;     // 和太小，左指针右移让和变大
        } else {
            --right;    // 和太大，右指针左移让和变小
        }
    }
    return {-1, -1};  // 无解
}

3.2 快慢指针模板（链表找中点）

// 快慢指针通用模板：找链表中点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* findMiddle(ListNode* head) {
    if (!head) return nullptr;
    ListNode* slow = head;   // 慢指针，一次走 1 步
    ListNode* fast = head;   // 快指针，一次走 2 步
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // 偶数个节点时返回前半段最后一个
}

四、示例一：两数之和 II（有序数组）

题目（LeetCode 167）：给定一个已升序排序的数组 numbers，找到两个数使其和等于目标 target。返回这两个数的下标（从 1 开始），且下标小的在前。保证恰好有一个解。

4.1 示例

输入：numbers = [2, 7, 11, 15]，target = 9
输出：[1, 2]（即 2 + 7 = 9）

4.2 C++ 代码

#include <vector>
using namespace std;

vector<int> twoSum(const vector<int>& numbers, int target) {
    int left = 0, right = (int)numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return {left + 1, right + 1};  // 题目要求下标从 1 开始
        } else if (sum < target) {
            ++left;     // 和太小，左指针右移
        } else {
            --right;    // 和太大，右指针左移
        }
    }
    return {-1, -1};  // 不会执行到，题目保证有解
}

这就是对撞模板的直接套用，注意返回时下标加 1 即可。如果题目没说"恰好一个解"，要在找到后继续移动指针收集所有解。

五、示例二：三数之和

题目（LeetCode 15）：给定数组 nums，找出所有和为 0 的不重复三元组。答案中不能包含重复的三元组。

5.1 思路：固定一个，对撞两个

三数之和是两数之和的扩展：先排序，再枚举第一个数 a = nums[i]，然后在 [i+1, n-1] 区间用对撞指针找两数之和等于 -a。去重的关键是相邻相同值跳过。

5.2 C++ 代码

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());  // 排序是对撞指针的前提
    int n = (int)nums.size();

    for (int i = 0; i < n - 2; ++i) {
        if (nums[i] > 0) break;  // 剪枝：a > 0 则三数之和必 > 0
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // a 去重

        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.push_back({nums[i], nums[left], nums[right]});
                // b、c 去重：跳过相邻相同值
                while (left < right && nums[left] == nums[left + 1]) ++left;
                while (left < right && nums[right] == nums[right - 1]) --right;
                ++left; --right;
            } else if (sum < 0) {
                ++left;
            } else {
                --right;
            }
        }
    }
    return res;
}

六、示例三：盛最多水的容器

题目（LeetCode 11）：给定 n 条垂直线，第 i 条高度为 height[i]，两线与 x 轴围成的容器能盛多少水。返回最大盛水量。

6.1 贪心思路：每次移动较矮的一侧

容器水量 = min(h[L], h[R]) * (R - L)。两个指针从两端向中间走，每次只移动较矮的一侧——因为移动较高的一侧不可能让水量增加（高度被较矮一侧限制，宽度反而变小）。

6.2 C++ 代码

#include <vector>
using namespace std;

int maxArea(const vector<int>& height) {
    int left = 0, right = (int)height.size() - 1;
    int bestArea = 0;
    while (left < right) {
        // 容器水量 = 短板高度 × 宽度
        int h = min(height[left], height[right]);
        int w = right - left;
        bestArea = max(bestArea, h * w);
        // 关键贪心：总是移动较矮的一侧
        if (height[left] < height[right]) {
            ++left;
        } else {
            --right;
        }
    }
    return bestArea;
}

七、总结与适用场景

典型题目清单

• LeetCode 167：两数之和 II（对撞，基础）
• LeetCode 15：三数之和（对撞 + 枚举）
• LeetCode 16：最接近的三数之和（对撞 + 枚举）
• LeetCode 11：盛最多水的容器（对撞 + 贪心）
• LeetCode 283：移动零（快慢同向）
• LeetCode 141/142：环形链表判环/找入口（快慢）
• LeetCode 876：链表的中间结点（快慢）
• LeetCode 344：反转字符串（对撞交换）
• LeetCode 125：验证回文串（对撞）