双指针问题详解

概述

双指针（Two Pointers）是一种重要的算法技巧，指的是在遍历元素的过程中，使用两个指针进行访问，从而达到相应的目的。

双指针的三种类型

对撞指针：两个指针方向相反，从两端向中间移动
快慢指针：两个指针方向相同，但移动速度不同
分离双指针：两个指针分别属于不同的数组/链表

时间复杂度优势

在数组的区间问题上，暴力算法的时间复杂度往往是 O(n²)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

1. 对撞指针（Two Pointers）

原理

对撞指针指的是两个指针 left、right 分别指向序列的第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left == right），或者满足其他要求的特殊条件为止。

求解步骤

使用两个指针 left、right
- left 指向序列第一个元素：left = 0
- right 指向序列最后一个元素：right = len(nums) - 1
在循环体中将左右指针相向移动
- 当满足一定条件时，将左指针右移：left += 1
- 当满足另外一定条件时，将右指针左移：right -= 1
直到两指针相撞（即 left == right），或者满足其他要求的特殊条件时，跳出循环体

通用模板

int left = 0, right = nums.size() - 1;
while (left < right) {  // 注意边界条件
    if (满足要求的特殊条件) {
        return 符合条件的值;
    } else if (一定条件1) {
        left++;
    } else if (一定条件2) {
        right--;
    }
}
return 没找到 或 找到对应值;

适用场景

有序数组问题：查找满足某些约束条件的一组元素，如两数之和、三数之和等
字符串问题：反转字符串、验证回文串、颠倒二进制等
容器问题：盛水最多的容器等

例题 1：两数之和 II - 输入有序数组

题目：给定一个已按非递减顺序排列的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数 target。

暴力解法

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); i++) {
            for (int j = i + 1; j < numbers.size(); j++) {
                if (numbers[i] + numbers[j] == target) {
                    return {i + 1, j + 1};
                }
            }
        }
        return {-1, -1};
    }
};

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

对撞指针解法

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum > target) {
                right--;  // 和太大，右指针左移
            } else {
                left++;   // 和太小，左指针右移
            }
        }
        return {-1, -1};
    }
};

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

关键思路：利用数组有序的特性，当两数之和大于目标值时，右指针左移；当两数之和小于目标值时，左指针右移。

例题 2：验证回文串

题目：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;

        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }

            // 比较字符（忽略大小写）
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }

            left++;
            right--;
        }
        return true;
    }
};

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

关键思路：

使用对撞指针从两端向中间移动
跳过非字母数字字符
比较字符时忽略大小写

例题 3：盛水最多的容器

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

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算当前面积
            int h = min(height[left], height[right]);
            int area = h * (right - left);
            maxArea = max(maxArea, area);

            // 移动较短的边（短板效应）
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};

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

关键思路：

使用对撞指针从两端开始
计算当前面积：面积 = min(height[left], height[right]) * (right - left)
移动较短的边（短板效应），因为移动较长的边不会增加面积

2. 快慢指针（Fast and Slow Pointers）

原理

快慢指针指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。

求解步骤

使用两个指针 slow、fast
- slow 一般指向序列第一个元素：slow = 0
- fast 一般指向序列第二个元素：fast = 1
在循环体中将指针向右移动
- 当满足一定条件时，将慢指针右移：slow += 1
- 当满足另外一定条件时（也可能不需要满足条件），将快指针右移：fast += 1
直到快指针移动到数组尾端（即 fast == len(nums) - 1），或者两指针相交，或者满足其他特殊条件时跳出循环体

通用模板

int slow = 0;
for (int fast = 1; fast < nums.size(); fast++) {
    if (满足要求的特殊条件) {
        slow++;
        nums[slow] = nums[fast];  // 可能需要赋值操作
    }
}
return slow + 1;  // 返回合适的值

适用场景

数组去重：删除有序数组中的重复元素
链表问题：判断链表是否有环、找链表中点、删除重复元素
移动零：将数组中的零移动到末尾
滑动窗口：某些滑动窗口问题的变种

例题 1：删除有序数组中的重复项

题目：给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int slow = 0;
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

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

关键思路：

slow 指针指向已处理数组的最后一个位置
fast 指针遍历整个数组
当 nums[fast] != nums[slow] 时，说明找到了新元素，将其放到 slow + 1 位置

例题 2：删除排序链表中的重复元素

题目：给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr) {
            if (fast->val != slow->val) {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }

        // 断开与后面重复元素的连接
        slow->next = nullptr;
        return head;
    }
};

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

关键思路：

slow 指针指向已处理链表的最后一个节点
fast 指针遍历整个链表
当遇到不同值的节点时，将其连接到 slow 后面

例题 3：删除排序链表中的重复元素 II

题目：给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;

        ListNode* pre = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            // 检查当前节点是否有重复
            if (curr->next != nullptr && curr->val == curr->next->val) {
                // 跳过所有重复的节点
                while (curr->next != nullptr && curr->val == curr->next->val) {
                    curr = curr->next;
                }

                // 删除重复的节点
                if (pre == nullptr) {
                    head = curr->next;  // 更新头节点
                } else {
                    pre->next = curr->next;
                }
            } else {
                pre = curr;  // 没有重复，更新pre指针
            }
            curr = curr->next;
        }

        return head;
    }
};

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

关键思路：

使用 pre 指针记录前一个非重复节点
当发现重复节点时，跳过所有重复节点
根据 pre 是否为空来决定如何删除重复节点

3. 分离双指针（Separate Two Pointers）

原理

分离双指针指的是两个指针分别属于不同的数组，两个指针分别在两个数组中移动。这种技巧常用于处理两个有序数组的合并、求交集、求并集等问题。

求解步骤

使用两个指针 left_1、left_2
- left_1 指向第一个数组的第一个元素：left_1 = 0
- left_2 指向第二个数组的第一个元素：left_2 = 0
根据条件移动指针
- 当满足一定条件时，两个指针同时右移：left_1 += 1、left_2 += 1
- 当满足另外一定条件时，将 left_1 指针右移：left_1 += 1
- 当满足其他一定条件时，将 left_2 指针右移：left_2 += 1
当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体

通用模板

int left_1 = 0, left_2 = 0;
while (left_1 < nums1.size() && left_2 < nums2.size()) {
    if (一定条件1) {
        left_1++;
        left_2++;
    } else if (一定条件2) {
        left_1++;
    } else if (一定条件3) {
        left_2++;
    }
}

适用场景

有序数组合并：合并两个有序数组
求交集：找出两个数组的交集
求并集：找出两个数组的并集
归并排序：归并两个有序子数组

例题：两个数组的交集

题目：给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 先排序，便于使用双指针
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        int left = 0, right = 0;
        vector<int> ans;

        while (left < nums1.size() && right < nums2.size()) {
            if (nums1[left] == nums2[right]) {
                // 避免重复添加相同元素
                if (ans.empty() || ans.back() != nums1[left]) {
                    ans.push_back(nums1[left]);
                }
                left++;
                right++;
            } else if (nums1[left] < nums2[right]) {
                left++;
            } else {
                right++;
            }
        }
        return ans;
    }
};

时间复杂度：O(m log m + n log n)，其中 m 和 n 分别是两个数组的长度
空间复杂度：O(1)，不考虑输出数组的空间

关键思路：

先对两个数组进行排序
使用分离双指针分别遍历两个数组
当元素相等时，添加到结果中（注意去重）
当元素不等时，移动较小元素对应的指针

总结

双指针算法是一种高效的算法技巧，通过合理使用两个指针可以显著降低时间复杂度：

三种双指针类型对比

类型	特点	适用场景	时间复杂度
对撞指针	从两端向中间移动	有序数组、回文串、容器问题	O(n)
快慢指针	同向移动，速度不同	数组去重、链表问题	O(n)
分离双指针	分别遍历不同数组	数组合并、求交集并集	O(m+n)

选择原则

对撞指针：适用于有序数组的两数之和、三数之和等问题
快慢指针：适用于数组去重、链表环检测等问题
分离双指针：适用于两个有序数组的合并、求交集等问题

注意事项

注意边界条件的处理
确保指针移动不会越界
根据题目要求正确处理重复元素
合理利用数组的有序性来优化算法