双指针算法原理与经典题目解析

算法原理讲解

正向遍历会导致覆盖未处理数据，因此采用反向遍历策略。

1. 寻找边界：创建 cur 和 dest 指针。dest 模拟扩展后的长度。遍历原数组，遇到 0 则 dest 加 2，否则加 1。找到最后一个需要复写的元素位置。
2. 处理越界：如果 dest 超出数组范围，说明最后一个 0 无法完全复写，需特殊处理（将末尾元素置 0，调整指针）。
3. 反向复写：从 cur 位置向前遍历，根据元素值决定 dest 的移动步数并赋值。

代码实现

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 快乐数 (LeetCode 202)

题目解析

判断一个整数是否是快乐数。快乐数定义为：将该数不断替换为其各个位置数字的平方和，最终结果为 1 则为快乐数；若陷入无限循环则不是。

算法原理讲解

此问题可转化为链表检测环的问题。定义快指针 fast 每次走两步，慢指针 slow 每次走一步。若两者相遇且值为 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 盛水最多的容器 (LeetCode 11)

题目解析

找出能盛最多水的容器，容积由两边界的距离乘以较短边的高度决定。

算法原理讲解

暴力解法时间复杂度为 O(N^2)。优化方案使用对撞指针：

1. 初始化 left = 0, right = height.size() - 1。
2. 计算当前容积，更新最大值。
3. 移动高度较小的指针（因为移动较高的一侧只会减小宽度且高度受限于短边，容积必然减小）。
4. 直到两指针相遇。

时间复杂度降为 O(N)。

代码实现

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 有效三角形的个数 (LeetCode 611)

题目解析

给定数组，统计能组成三角形的三元组个数。三角形成立条件：任意两边之和大于第三边。

算法原理讲解

暴力枚举为 O(N^3)。优化步骤：

1. 先将数组排序。
2. 固定最大边 i（从后往前），使用双指针 left 和 right 在 i 左侧寻找满足条件的两边。
3. 若 nums[left] + nums[right] > nums[i]，则 left 到 right-1 的所有元素均满足条件，计数增加 right - left，然后 right--。
4. 否则 left++。

时间复杂度 O(N^2)。

代码实现

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 的两个数字 (LeetCode LCR 179)

题目解析

在升序数组中找出两个元素，使其和为 target。

算法原理讲解

利用数组有序特性，使用对撞指针：

1. left 指向首元素，right 指向尾元素。
2. 若和大于 target，right--。
3. 若和小于 target，left++。
4. 相等则返回结果。

时间复杂度 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 三数之和 (LeetCode 15)

题目解析

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

算法原理讲解

1. 排序数组。
2. 固定第一个数 i，转化为两数之和问题。
3. 使用双指针 left 和 right 在 i 右侧查找。
4. 注意去重：跳过相同的 i，以及找到结果后跳过相同的 left 和 right。

时间复杂度 O(N^2)。

代码实现

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 四数之和 (LeetCode 18)

题目解析

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

算法原理讲解

在三数之和基础上增加一层循环固定第二个数 j。

1. 排序数组。
2. 固定 i 和 j，转化为两数之和问题。
3. 注意数据类型溢出，求和时使用 long long。
4. 同样需要对 i, j, left, right 进行去重处理。

时间复杂度 O(N^3)。

代码实现

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;
    }
};