367. Valid Perfect Square

O(sqrt(n))
n² - (n - 1)² = (n + (n - 1)) * (n - (n - 1)) = 2n-1
e.g., 16 = 1 + 3 + 5 + 7

class Solution {
public:
    bool isPerfectSquare(int num) {
        for (int i = 1; num > 0; i += 2) {
            num -= i;
        }
        return num == 0;
    }
};

用这个
O(logn)

class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) { // 小于等于可行，因为只需要找
            long m = l + (r - l) / 2;
            long p = m * m;
            if (p == num) {
                return true;
            } else if (p < num) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return false;
    }
};

Newton method

class Solution {
public:
    bool isPerfectSquare(int num) {
        long x = num;
        while (x * x > num) {
            x = (x + num / x) >> 1;
        }
        return x * x == num;
    }
};