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

1089. 复写零

题目描述

在一个固定的整数数组中，将每个出现的 0 复写一遍，并将后续元素向右移动。超出原数组长度的元素将被丢弃。

核心思路

直接从前向后遍历会导致覆盖未处理的数据。最优解法是先计算需要复写的范围，再从后向前操作。

1. 确定边界：使用双指针模拟复写过程，找到最后一个有效元素的位置。dest 指针模拟复写后的索引，当 dest >= size - 1 时停止。
2. 处理边缘情况：如果最后一个有效元素是 0，它可能只能复写一次（因为空间不足），需单独判断。
3. 倒序写入：从找到的有效位置开始，cur 向左移动，dest 指向数组末尾。遇到非零元素写一次，遇到 0 写两次。

代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int size = arr.size();

        // 第一步：确定最后一个有效元素的位置
        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. 快乐数

题目描述

编写一个算法来判断一个数 n 是否是快乐数。快乐数的定义是：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 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) 处的垂直线高度。找出两条线，使得它们与 x 轴共同构成的容器能容纳最多的水。

核心思路

这是一个典型的对撞指针应用场景。

• 容器的面积由 min(height[left], height[right]) * (right - left) 决定。
• 随着指针向内移动，宽度 (right - left) 必然减小。
• 为了获得更大的面积，必须提高高度。因此，我们每次移动高度较小的那一侧的指针，试图找到更高的边界。

代码实现

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