Сумма квадратов

Доно неотрицательное целое число c, нужно определить, существуюь ли два целых числа a иb, что a² + b² = c.

Пример 1:

Дано: 5
Ответ: True
Пояснение: 1 * 1 + 2 * 2 = 5

Пример 2:

Дано: 3
Ответ: False

Компилируемое решение

public class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b)
                return true;
        }
        return false;
    }
}

Анализ сложности

• Сложность по времени : $O\big(\sqrt{c}\log c\big)$. Мы ищем среди $\sqrt{c}$ значений, чтобы определить $a$. Для каждого выбранного $a$, нахождение квадратного корня из $c - a^2$ занимает $O\big(\log c\big)$ времени в худшем случае.
• Сложность по памяти : $O(1)$. Постоянное количество переменных используется.