双指针算法实战：快乐数与盛最多水的容器

快乐数

题目描述

判断一个正整数是否为快乐数。如果一个数经过以下操作最终变为 1，则它是快乐数：将各位数字平方后求和。否则，它不是快乐数。

原理解析

要判断是否快乐，关键在于检测是否存在循环。根据鸽巢原理，数字变换后的结果必然落入有限区间（对于 21 亿以内的数，各位平方和最大为 810）。这意味着无论怎么变换，数值迟早会重复。一旦重复，就进入了死循环。

我们可以使用快慢指针来检测循环。定义两个指针，慢指针每次走一步，快指针每次走两步。如果存在循环且包含 1，快慢指针最终会在 1 处相遇；如果循环不包含 1，它们会在循环内的某点相遇。

代码实现

// 计算各位数字的平方和
int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

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

盛最多水的容器

题目描述

给定一个非负整数数组，代表高度，找出两条线使得它们与 x 轴共同构成的容器能容纳最多的水。

原理解析

容器的容量取决于宽度（两线距离）和高度（较短的那条线）。公式为：面积 = 距离 × min(左高，右高)。

使用双指针，分别指向数组首尾。计算当前面积并更新最大值。为了获得更大的面积，我们需要尝试增加高度。由于宽度会随着指针相向移动而减小，只有移动较短的那条边，才有可能遇到更高的边从而增加面积。如果移动较长的边，高度只会变低或不变，面积必然减小。

代码实现

int maxArea(int* height, int heightSize) {
    int left = 0;
    int right = heightSize - 1;
    int maxV = 0;
    
     (left < right) {
         h = height[left] < height[right] ? height[left] : height[right];
         w = right - left;
         currentArea = h * w;
        
         (currentArea > maxV) {
            maxV = currentArea;
        }
        
         (height[left] < height[right]) {
            left++;
        }  {
            right--;
        }
    }
     maxV;
}