双指针算法技巧全场景拆解：从数组操作到环检测

引言

在算法题中，双指针技巧是一类高频且实用的解题方法。它并非真正的'指针'，而是通过两个数组下标（或迭代器）的协同移动，在数组划分、区间求解、环检测等场景中实现高效遍历与逻辑处理，往往能将时间复杂度从暴力法的 O(n^2) 优化至 O(n)，是解决数组类难题的关键。

双指针概述

常用于：数组划分和数组分块

注意：这里的指针不是真的指针，是数组的下标

经典例题解析

移动零

题目链接： 283. 移动零

思路：

• cur：从左往右遍历数组
• dest：已处理区间内，非零元素的最后一个位置

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        for (; cur < nums.size(); cur++) {
            if (nums[cur] != 0) {
                swap(nums[dest + 1], nums[cur]);
                dest++;
            }
        }
    }
};

复写零

题目链接： 1089. 复写零

思路：

1. 先找到最后一个被复写的数。判断 cur 位置的值，cur 放到下标 0 位置，dest 放到下标 -1 位置。
2. 如果 dest 超过最后那个数的位置，需特殊处理。
3. 从后向前完成复写操作。

注意：

• vector 的 size()-1 就是最后一个位置的下标，区分元素和下标。
• 区分 == 和 =。
• size() 在用来表示下标的时候，建议赋值给 int 类型后再用，否则涉及无符号整数提升可能导致问题。

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        for (; dest < (int)arr.size() - 1; cur++) {
            if (arr[cur] == 0) dest++;
            dest++;
        }
        cur--;
        if (dest == arr.size()) {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        }
        for (; cur >= 0; cur--) {
            arr[dest] = arr[cur];
            if (arr[cur] == 0) arr[--dest] = 0;
            dest--;
        }
    }
};

快乐数

题目链接： 202. 快乐数

思路： 结果只有两种可能：为 1 或者无限循环。对于无限循环的情况，可以使用快慢双指针去解决（类似链表判环）。快慢指针的起点都是 n，快慢指针一定会在环入口相遇。

class Solution {
public:
    int algorithm(int p) {
        int sum = 0;
        while (p >= 10) {
            int q = p % 10;
            p /= 10;
            sum += q * q;
        }
        sum += p * p;
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = n;
        slow = algorithm(slow);
        fast = algorithm(algorithm(fast));
        while (slow != fast) {
            slow = algorithm(slow);
            fast = algorithm(algorithm(fast));
        }
        return slow == 1;
    }
};

盛最多水的容器

题目链接： 11. 盛最多水的容器

思路：

• left 放在最左边，right 放在最右边。
• 比较之后，看 left 和 right 哪个对应的值小些，就把哪个向另外一边靠近。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int max1 = 0;
        while (left != right) {
            max1 = max(max1, (right - left) * min(height[right], height[left]));
            if (height[left] < height[right]) left++;
            else right--;
        }
        return max1;
    }
};

有效三角形的个数

题目链接： 611. 有效三角形的个数

思路：

• 相关数学知识：三角形最小的那两边之和 > 最大那一边就可以构成三角形了。
• 方法：先给数组排序，然后先固定最大的数，在最大的数的左边用双指针算法去找符合的数；然后再缩小最大的数。
• 注意：如果 nums[left] + nums[right] > nums[c]，那么 right - left 就是第二大数下标为 right 时的总个数，然后 right--。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int c = nums.size() - 1;
        int ret = 0;
        while (c >= 2) {
            int left = 0;
            int right = c - 1;
            while (left != right) {
                if ((nums[left] + nums[right]) > nums[c]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
            c--;
        }
        return ret;
    }
};

查找总价格为目标值的两个商品

题目链接： 两数之和 II - 输入有序数组

思路：

• 这个题有单调性，用双指针正好（或者二分算法），能用双指针肯定优先用双指针。
• 注意：此题没说找不到怎么办，就不用管那种情况，但是力扣要求所有路径都要有返回值，在最后加个 return 即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;
        int left = 0;
        int right = price.size() - 1;
        while (left != right) {
            if (price[left] + price[right] > target) right--;
            else if (price[left] + price[right] < target) left++;
            else {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};

三数之和

题目链接： 三数之和

思路：

• 这种和怎么样怎么样的一般都排序之后用双指针。
• 细节问题：
  1. 去重：left 和 right 以及固定的那个数都要跳过重复元素（哪个跟哪个比较 == 才去要注意），同时要避免越界，比如 left 一直要 < right。
  2. 不漏：找到一种结果之后，不能直接 break 出去，要继续寻找，例如 left++; right--;。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int size = nums.size();
        for (int k = 0; k < size - 2; k++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1;
            int j = size - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum > 0) j--;
                else if (sum < 0) i++;
                else {
                    ret.push_back({nums[k], nums[i], nums[j]});
                    i++;
                    j--;
                    while (i < j && nums[i] == nums[i - 1]) i++;
                    while (i < j && nums[j] == nums[j + 1]) j--;
                }
            }
        }
        return ret;
    }
};