202. 快乐数

Problem: 202. 快乐数

思路

主要是计算sum,后面的步骤与一般查找相同,如果存在相同sum则说明不是快乐数,如果sum == 1则说明是快乐数

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

Code

class Solution {
public:
    int getSum(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if(n == 1) return true;
            if(set.find(sum) != set.end())
                return false;
            else
                set.insert(sum);
            n = sum;
        }
    }
};