博客详情 - oirush

admin 的博客
双指针算法 (Two Pointers)
admin SU @ 2026-6-7 19:59:14

算法概述

双指针（Two Pointers）是一种使用两个指针在数组、链表或字符串等线性数据结构上进行遍历的算法技巧。通过两个指针的协同移动，可以在单次遍历中解决许多需要两重循环才能解决的问题，将时间复杂度从 O(n²) 降低到 O(n)。

双指针并非一个特定的算法，而是一种解题思想/技巧。根据指针的移动方向和用途不同，双指针可分为多种子类型。

核心思想

双指针的核心在于利用问题的某种单调性或有序性，让两个指针分别从不同位置出发，通过巧妙的移动策略在一次遍历中定位答案，避免不必要的重复计算。

常见子类型：

类型	描述	典型应用
左右指针	从两端向中间移动	两数之和、盛水容器、回文串判断
快慢指针	一快一慢同向移动	链表找环、找中点
滑动型双指针	同时维护左右边界，区间不断滑动（即滑动窗口）	见《滑动窗口》篇
归并型双指针	两个指针分别遍历两个有序序列并合并	合并两个有序数组

算法步骤 / 伪代码

场景 1：左右指针 — 有序数组的两数之和

function twoSumSorted(arr, target):
    left = 0
    right = arr.length - 1
    while left < right:
        sum = arr[left] + arr[right]
        if sum == target:
            return [left, right]
        else if sum < target:
            left++                         // 和太小，左指针右移增大和
        else:
            right--                        // 和太大，右指针左移减小和
    return [-1, -1]

场景 2：快慢指针 — 链表找环（Floyd 判圈算法）

function hasCycle(head):
    slow = head
    fast = head
    while fast != null and fast.next != null:
        slow = slow.next                  // 慢指针走 1 步
        fast = fast.next.next             // 快指针走 2 步
        if slow == fast:
            return true                   // 有环
    return false

场景 3：归并型双指针 — 合并两个有序数组

function merge(arr1, arr2):
    i = 0, j = 0
    result = []
    while i < arr1.length and j < arr2.length:
        if arr1[i] <= arr2[j]:
            result.append(arr1[i]);  i++
        else:
            result.append(arr2[j]);  j++
    while i < arr1.length: result.append(arr1[i++])
    while j < arr2.length: result.append(arr2[j++])
    return result

C++ 代码实现

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

// ============ 场景 1：左右指针 — 两数之和（有序数组）============
vector<int> twoSumSorted(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            ++left;    // 和太小，增大
        } else {
            --right;   // 和太大，减小
        }
    }
    return {-1, -1};   // 未找到
}

// ============ LeetCode 11：盛最多水的容器 ============
int maxArea(const vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxWater = 0;

    while (left < right) {
        int h = min(height[left], height[right]);
        int w = right - left;
        maxWater = max(maxWater, h * w);

        // 核心：移动较短的那一边，因为移动较长边不会使容量增大
        if (height[left] < height[right]) {
            ++left;
        } else {
            --right;
        }
    }
    return maxWater;
}

// ============ 场景 2：快慢指针 — 链表找环 ============

// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// LeetCode 141：判断链表是否有环
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// LeetCode 142：找到环的入口节点
ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    // 第一阶段：判断是否有环，并让快慢指针相遇
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 第二阶段：从头和相遇点同时出发，再次相遇处即为环入口
            ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;   // 环的入口
        }
    }
    return nullptr;       // 无环
}

// 快慢指针找链表中点
ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// ============ 场景 3：归并型双指针 — 合并两个有序数组 ============
vector<int> mergeTwoSorted(const vector<int>& a, const vector<int>& b) {
    int i = 0, j = 0;
    vector<int> result;
    result.reserve(a.size() + b.size());

    while (i < a.size() && j < b.size()) {
        if (a[i] <= b[j]) {
            result.push_back(a[i++]);
        } else {
            result.push_back(b[j++]);
        }
    }
    while (i < a.size()) result.push_back(a[i++]);
    while (j < b.size()) result.push_back(b[j++]);

    return result;
}

// ============ 场景 4：LeetCode 15 — 三数之和（排序 + 双指针）============
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    int n = nums.size();
    if (n < 3) return result;

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

    for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重

        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                // 跳过重复元素
                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 result;
}

// ============ 主函数 ============
int main() {
    cout << "========== 双指针算法演示 ==========" << endl << endl;

    // ---- 场景 1：两数之和（有序数组）----
    vector<int> sortedArr = {2, 7, 11, 15, 18, 22};
    int target = 33;
    auto res = twoSumSorted(sortedArr, target);
    cout << "【两数之和（有序数组）】" << endl;
    cout << "数组: ";
    for (int x : sortedArr) cout << x << " ";
    cout << "\n目标和: " << target << endl;
    if (res[0] != -1) {
        cout << "找到: arr[" << res[0] << "]=" << sortedArr[res[0]]
             << " + arr[" << res[1] << "]=" << sortedArr[res[1]]
             << " = " << target << endl;
    } else {
        cout << "未找到" << endl;
    }

    // ---- LeetCode 11：盛最多水的容器 ----
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << "\n【LeetCode 11：盛最多水的容器】" << endl;
    cout << "高度: ";
    for (int h : height) cout << h << " ";
    cout << "\n最大容量: " << maxArea(height) << " (期望: 49)" << endl;

    // ---- 场景 2：快慢指针 — 链表 ----
    // 构建带环链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 ...
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5; n5->next = n3; // 环

    cout << "\n【LeetCode 141：环形链表】" << endl;
    cout << "链表有环: " << (hasCycle(n1) ? "是" : "否") << " (期望: 是)" << endl;
    ListNode* entry = detectCycle(n1);
    if (entry) {
        cout << "环的入口节点值: " << entry->val << " (期望: 3)" << endl;
    }

    // 无环链表的中点
    ListNode* head2 = new ListNode(1);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(3);
    head2->next->next->next = new ListNode(4);
    head2->next->next->next->next = new ListNode(5);
    cout << "无环链表中点值: " << findMiddle(head2)->val << " (期望: 3)" << endl;

    // ---- 场景 3：合并两个有序数组 ----
    vector<int> a = {1, 3, 5, 7, 9};
    vector<int> b = {2, 4, 6, 8, 10};
    auto merged = mergeTwoSorted(a, b);
    cout << "\n【合并两个有序数组】" << endl;
    cout << "A: "; for (int x : a) cout << x << " "; cout << endl;
    cout << "B: "; for (int x : b) cout << x << " "; cout << endl;
    cout << "合并后: "; for (int x : merged) cout << x << " "; cout << endl;

    // ---- LeetCode 15：三数之和 ----
    vector<int> threeSumArr = {-1, 0, 1, 2, -1, -4};
    cout << "\n【LeetCode 15：三数之和】" << endl;
    cout << "数组: ";
    for (int x : threeSumArr) cout << x << " ";
    cout << endl;
    auto triplets = threeSum(threeSumArr);
    cout << "和为 0 的三元组:" << endl;
    for (auto& t : triplets) {
        cout << "  [" << t[0] << ", " << t[1] << ", " << t[2] << "]" << endl;
    }

    return 0;
}

复杂度分析

场景	时间复杂度	空间复杂度	说明
左右指针	O(n)	O(1)	两个指针各遍历一次
快慢指针	O(n)		快指针最多遍历完整链表
归并型双指针	O(n + m)		分别遍历两个序列
三数之和	O(n²)		外循环 O(n) × 内循环双指针 O(n)

双指针的核心价值在于将嵌套循环压缩到单层遍历，使时间复杂度大幅降低。

应用场景

两数之和（有序数组）：在一个有序数组中找两个数使它们的和为特定值。左右指针的经典应用。
盛最多水的容器：LeetCode 11，用左右指针从两端向中间靠拢，每次移动较短的边。
链表问题：
- 判断链表是否有环（LeetCode 141）
- 找环的入口（LeetCode 142）
- 找链表中点
- 找链表倒数第 K 个节点
合并有序序列：合并两个有序数组/链表，归并排序的合并步骤。
三数之和 / 四数之和：先排序固定一个数，再用双指针转化为两数之和问题。
回文串判断：左右指针从两端向中间比较字符。
去重 / 移除元素：快慢指针原地修改数组（LeetCode 26/27/283）。

经典例题

LeetCode 11 — 盛最多水的容器

题目描述：给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两端是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

示例：

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

双指针解法思路：

左右指针初始分别指向数组两端。
计算当前面积 = min(height[left], height[right]) × (right - left)。
总是移动较短的那一边（因为移动较长边不会增加面积，宽度减少只会使面积更小）。
直到左右指针相遇，记录过程中出现的最大面积。

LeetCode 141 — 环形链表

题目描述：给你一个链表的头节点 head，判断链表中是否有环。

快慢指针（Floyd 判圈算法）思路：

快指针每次走两步，慢指针每次走一步。
如果存在环，快指针最终会追上慢指针（在环内从后面追上）。
如果不存在环，快指针会先到达链表末尾。

（完整 C++ 代码已包含在上方的代码实现中）

双指针算法 (Two Pointers)

算法概述

核心思想

算法步骤 / 伪代码

场景 1：左右指针 — 有序数组的两数之和

场景 2：快慢指针 — 链表找环（Floyd 判圈算法）

场景 3：归并型双指针 — 合并两个有序数组

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 11 — 盛最多水的容器

LeetCode 141 — 环形链表

状态

开发

支持

关于

双指针算法 (Two Pointers)

算法概述

核心思想

算法步骤 / 伪代码

场景 1：左右指针 — 有序数组的两数之和

场景 2：快慢指针 — 链表找环（Floyd 判圈算法）

场景 3：归并型双指针 — 合并两个有序数组

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 11 — 盛最多水的容器

LeetCode 141 — 环形链表

状态

开发

支持

关于

还没有账户？

登录