双指针算法详解：原理与经典题目实战

2.2 复写零

1089. 复写零 - LeetCode

题目解析

将数组中的每个 0 复写一遍，非 0 元素保持不变。要求就地实现，不能申请新内存空间。

算法原理讲解

正向遍历时，若直接复写会导致后续元素被覆盖。因此采用从后向前遍历的策略。

步骤：

1. 初始化 cur = 0, dest = -1。
2. 找到最后一个需要复写的数：遍历原数组，遇到 0 则 dest 移两位，否则移一位。直到 dest 越界或到达末尾。
3. 处理特殊情况：如果最后一个复写的数是 0 且导致 dest 越界，需单独处理边界。
4. 从 cur 位置开始往前遍历，依次还原复写后的结果。

代码实现

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

2.3 快乐数

202. 快乐数 - LeetCode

题目解析

判断给定整数是否是快乐数。快乐数定义为不断替换成其各位数字平方之和，最后循环结果为 1。

算法原理讲解

使用快慢指针检测循环。快指针每次走两步，慢指针每次走一步。若相遇且值为 1，则是快乐数；否则不是。

代码实现

class Solution {
public:
    int getsum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int fast = getsum(getsum(n));
        int slow = getsum(n);
        while(slow != fast) {
            fast = getsum(getsum(fast));
            slow = getsum(slow);
        }
        return slow == 1;
    }
};

2.4 盛水最多的容器

11. 盛最多水的容器 - LeetCode

题目解析

找出能盛最多水的容器。容积 = 两边距离 × 短边高度。

算法原理讲解

暴力解法时间复杂度 O(N^2)。优化方案使用双指针，初始分别指向首尾。每次移动较短的一边，因为移动较长边只会减小宽度且高度不会增加，容积必然减小。

代码实现

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

2.5 有效三角形的个数

611. 有效三角形个数 - LeetCode

题目解析

统计数组中能组成三角形的三元组个数。任意两边之和大于第三边。

算法原理讲解

暴力枚举 O(N^3)。优化方法：先排序，固定最大边 i，使用双指针 left 和 right 寻找另外两边。若 nums[left] + nums[right] > nums[i]，则 left 到 right-1 的所有元素均满足条件。

代码实现

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

2.6 和为 s 的两个数字

LCR 179. 查找总价格为目标值的两个商品 - LeetCode

题目解析

在升序数组中找出两数之和等于 target 的二元组。

算法原理讲解

使用双指针 left 和 right 分别指向首尾。根据当前和与 target 的大小关系移动指针。时间复杂度 O(N)。

代码实现

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

2.7 三数之和

15. 三数之和 - LeetCode

题目解析

找出所有和为 0 且不重复的三元组。

算法原理讲解

先排序，固定一个数 a，转化为两数之和问题。使用双指针在剩余区间查找。注意去重：跳过相同的 a、left 和 right。

代码实现

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

2.8 四数之和

18. 四数之和 - LeetCode

题目解析

找出所有和为 target 且不重复的四元组。

算法原理讲解

类似三数之和，固定两个数，剩余部分使用双指针。注意数据类型溢出问题，求和时使用 long long。

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> v;
        int n = nums.size();
        for(int i = 0; i < n;) {
            for(int j = i + 1; j < n;) {
                long long count2 = (long long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;
                while(left < right) {
                    int count1 = nums[left] + nums[right];
                    if(count1 > count2) right--;
                    else if(count1 < count2) left++;
                    else {
                        v.push_back({nums[left], nums[right], nums[i], nums[j]});
                        left++, right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                j++;
                while(j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return v;
    }
};