LeetCode 202 快樂數：集合檢測循環 vs 快慢指針 O(1) 空間

問題描述

「快樂數」定義：對一個正整數，反覆替換為其各位數字平方和，最終若變為 1 則為快樂數；否則會陷入不包含 1 的循環。判斷給定數 n 是否為快樂數。

核心觀察：必然進入循環

對於 32 位整數，最大平方和為 9²×10 = 810。故過程會迅速進入 [1, 810] 範圍，狀態有限，必然循環。檢測循環即可判斷。

解法一：HashSet 記錄已見數值 (O(n) 空間)

public boolean isHappy(int n) {
    Set seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n == 1;
}
private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

解法二：快慢指針檢測循環 (O(1) 空間，Floyd 算法)

慢指針每次走一步 n = getNext(n)，快指針每次走兩步 n = getNext(getNext(n))。若相遇且不為 1，則有環；若快指針變為 1，則為快樂數。

public boolean isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    } while (slow != fast);
    return slow == 1;
}

複雜度對比

數學補充：唯一非快樂循環

對於十進制，非快樂數最終都會進入循環：4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。故也可直接判斷 n == 4 作為終止條件（但快慢指針更通用）。

總結

LeetCode 202 是「快慢指針檢測循環」在數字序列上的完美應用。掌握此模板，可解決「環形鏈表、數字循環、狀態機循環」等所有循環檢測問題，且達到 O(1) 空間最優。