什么是双指针法？(What is the Two-Pointers Technique?)

双指针（Two Pointers）是一种算法设计思想，它通过在数据结构（通常是数组或链表）上维护两个指针，并让它们以一定的规则移动，从而协同完成任务。

这里的“指针”并非 C/C++ 中的内存地址指针，而更多是指索引 (index) 或迭代器 (iterator)，用来标记数据序列中的位置。

核心目标：双指针法的主要目标通常是将一些需要嵌套循环（时间复杂度为 O(n²)）才能解决的问题，优化为只需一次遍历（时间复杂度为 O(n)）即可解决。它通过巧妙的指针移动，减少了不必要的计算和比较。

通俗比喻：

想象一下在一条长长的跑道上，有两个运动员。我们可以让他们：

一个跑得快，一个跑得慢（快慢指针）。
从跑道的两端同时出发，相向而行（左右指针）。
都从起点出发，但保持一定距离，像一个“窗口”一样前进（滑动窗口）。

通过观察这两个运动员的位置关系和他们所在位置的“风景”（数据），我们就能高效地解决问题。

双指针法的三种主要模式

双指针主要有以下三种经典的模式

1. 快慢指针 (Fast & Slow Pointers)

这种模式下，两个指针从同一端点出发，但移动速度不同。快指针 fast 负责在前面探索，慢指针 slow 负责处理“已确认”的部分。

典型应用1：移动零

问题：将所有 0 移动到数组末尾，保持非零元素相对顺序。

思想：

slow 指针：指向下一个非零元素应该被放置的位置。
fast 指针：遍历整个数组，寻找非零元素。
更进一步地, 这种方式也叫做前后指针, 一个指向已处理的部分，一个指向未处理的部分

过程：

fast 向前移动，如果 nums[fast] 不是 0，就说明找到了一个需要保留的元素。
将这个非零元素放到 slow 指针的位置 nums[slow] = nums[fast]。
slow 指针前进一步，为下一个非零元素腾出位置。
fast 无论如何都前进一步。

优势：通过一次遍历就完成了元素的“去芜存菁”和重新排列。

典型应用2：判断链表是否有环

问题：给定一个链表，判断其中是否存在环。

思想：

slow 指针：每次移动一步。
fast 指针：每次移动两步。
这种方式则和上一种方式不同, 它是两个指针都在处理同一部分数据, 只是速度不同.

过程：

两个指针从链表头同时出发。
如果在某个时刻，fast 指针追上了 slow 指针（即 fast == slow），说明链表中存在环。
如果 fast 指针到达了链表的末尾（即 fast == nullptr 或 fast->next == nullptr），说明没有环。

2. 左右指针 (Left & Right Pointers)

也称为“对撞指针”或“首尾指针”。两个指针分别位于数据序列的两端，然后根据特定条件向中间移动。这种模式通常适用于已经排好序的数组。

典型应用：两数之和 II - 输入有序数组

问题：在一个升序数组中，找到两个数，使它们的和等于目标值 target。

思想：

left 指针：指向数组开头，即最小值。
right 指针：指向数组末尾，即最大值。

过程：

计算 sum = nums[left] + nums[right]。
如果 sum == target，恭喜，找到了！
如果 sum < target，说明当前的和太小了，需要增大总和，所以让 left 指针向右移动一位（left++）。
如果 sum > target，说明当前的和太大了，需要减小总和，所以让 right 指针向左移动一位（right--）。
循环直到 left 和 right 相遇。

优势：通过在两端逼近，每次迭代都能排除一个不可能的选项，将 O(n²) 的暴力搜索优化为 O(n)。

示例:三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

#include <vector>
#include <algorithm> // 用于 std::sort

class Solution {
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::vector<std::vector<int>> ans;
        int n = nums.size();

        if (n < 3) {
            return ans; // 元素个数不足 3
        }

        // 1. 排序：这是去重的基础
        std::sort(nums.begin(), nums.end());

        // 2. 外层循环：固定第一个数 a (nums[i])
        for (int i = 0; i < n - 2; ++i) {
            
            // 优化：如果固定的数 a > 0，则 b+c 必须 < 0。
            // 但 b 和 c 都在 a 的右侧 (b, c >= a)，所以 b+c 必定 >= 0。
            // 因此，如果 nums[i] > 0，不可能有解。
            if (nums[i] > 0) {
                break;
            }

            // 关键（去重 a）：如果当前的 nums[i] 与上一个相同，
            // 则它会找到完全相同的 b 和 c 组合，必须跳过。
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 3. 双指针（2Sum）：在 [i+1 ... n-1] 中寻找 b 和 c
            int left = i + 1;
            int right = n - 1;
            int target = -nums[i]; // 目标：nums[left] + nums[right] == target

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == target) {
                    // 找到了一个三元组
                    ans.push_back({nums[i], nums[left], nums[right]});

                    // 关键（去重 b 和 c）：
                    // 跳过所有与当前 nums[left] 相同的元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 跳过所有与当前 nums[right] 相同的元素
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 移动指针，寻找下一对
                    left++;
                    right--;

                } else if (sum < target) {
                    // 和太小，左指针右移
                    left++;
                } else { // sum > target
                    // 和太大，右指针左移
                    right--;
                }
            }
        }

        return ans;
    }
};

3. 滑动窗口 (Sliding Window)

这可以看作是快慢指针的一种特例，两个指针 start 和 end 构成一个“窗口”。窗口通常会先扩大（移动 end 指针），然后在满足一定条件后缩小（移动 start 指针），整个过程就像一个窗口在数据上滑动。

典型应用：长度最小的子数组

问题：给定一个正整数数组和一个目标值 s，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。

思想：

start 指针：窗口的左边界。
end 指针：窗口的右边界。
维护一个变量 window_sum 记录窗口内元素的和。

过程：

扩大窗口：end 指针不断向右移动，并将新元素加入 window_sum。
判断与收缩窗口：一旦 window_sum ≥ s，就说明找到了一个满足条件的窗口。
记录下当前窗口的长度 end - start + 1，并与已记录的最小长度比较。
尝试缩小窗口：从 window_sum 中减去 nums[start] 的值，并将 start 指针向右移动。
持续缩小，直到 window_sum < s，然后再去扩大窗口。
重复此过程，直到 end 到达数组末尾。

优势：巧妙地避免了对所有可能的子数组进行求和的暴力计算。每个元素最多被访问两次（一次被 end 指针扫过，一次被 start 指针扫过），时间复杂度为 O(n)。

总结：何时考虑使用双指针？

当遇到一个问题，特别是涉及数组或链表时，如果发现有以下特征，可以优先考虑双指针法：

需要进行原地操作：要求空间复杂度为 O(1)，直接在原数组上修改，如“移动零”。
涉及有序数组的配对问题：需要在有序数组中寻找满足特定和、差、积的数对，如“两数之和 II”。
寻找连续子数组/子串的极值问题：要求满足某个条件的“最长”、“最短”、“最大”、“最小”的连续子数组，如“长度最小的子数组”、“无重复字符的最长子串”。
链表问题：判断环、寻找中点、合并两个有序链表等。

总之, 双指针法是一种“降维”思想，它将二维的搜索空间（嵌套循环）压缩到一维（线性扫描），是提升算法效率的强大工具。