双指针算法实战：移动零、复写零与快乐数

代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int size = arr.size();
        
        // 第一遍：计算 dest 位置
        while (dest < size - 1) {
            if (arr[cur] == 0) dest += 2;
            else dest++;
            if (dest < size - 1) cur++;
        }
        
        // 处理边界情况：最后一个 0 只能复写一次
        if (dest >= size) {
            arr[size - 1] = 0;
            dest = size - 2;
            cur--;
        }
        
        // 第二遍：从后往前填充
        while (cur >= 0) {
            if (arr[cur] == 0) {
                arr[dest--] = 0;
                arr[dest--] = 0;
            } else {
                arr[dest--] = arr[cur];
            }
            cur--;
        }
    }
};

202. 快乐数

题目描述

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。重复这个过程直到这个数变为 1，或者无限循环但始终变不到 1。如果是 1，则为快乐数。

思路解析

这个问题本质是判断是否存在环。对于每个非零整数，经过不断求和，要么最终得到 1，要么进入循环。我们可以使用快慢指针来检测循环。

• 慢指针走一步：对应一次求和。
• 快指针走两步：对应连续求和两次。
• 结束条件：快慢指针相遇。
• 判断：如果相遇时值为 1，则是快乐数；否则不是。

代码实现

class Solution {
public:
    int Sum(int n) {
        int sum = 0;
        while (n) {
            int a = n % 10;
            sum += pow(a, 2);
            n /= 10;
        }
        return sum;
    }

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

11. 盛水最多容器

题目描述

给定 n 个非负整数 a1, a2, ..., an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

思路解析

暴力解法需要 O(n^2) 时间。利用对撞指针可以将复杂度降为 O(n)。

容器的体积 V = 宽度 * 高度。宽度由左右指针距离决定，高度由较短的那条线决定。当左右指针向内移动时，宽度一定变短。为了获得更大的体积，必须找到更高的高度。

策略：让高度较小的指针向内移动，尝试寻找更高的线。每次移动后计算当前体积并更新最大值。

代码实现

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

以上四个案例涵盖了双指针的主要应用场景。实际编码时，务必注意指针边界条件和数组越界风险。