633 Sum of Square Numbers

633. Sum of Square Numbers

1. Question

Given a non-negative integerc, your task is to decide whether there're two integersaandbsuch that a2+ b2= c.

Example 1:

Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3

Output: False

2. Implementation

(1) Binary Search

class Solution {
    public boolean judgeSquareSum(int c) {
        for (long num = 0; num <= (long)Math.sqrt(c); num++) {
            long target = c - num * num;

            if (isSquareNum(0, target, target)) {
                return true;
            }
        }
        return false;
    }

    public boolean isSquareNum(long start, long end, long target) {
        long mid = 0;

        while (start <= end) {
            mid = start + (end - start)/2;

            if (mid * mid == target) {
                return true;
            }
            else if (mid * mid < target) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        return false;
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度Sqrt(n) * log(Sqrt(n)), n为输入的数字，空间复杂度O(1)