Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.

 

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

 

Example 2:

Input: 3
Output: False

 

Approach #1: Math. [Java]

class Solution {
    public boolean judgeSquareSum(int c) {
        if (c < 0) return false;
        int l = 0, r = (int)Math.sqrt(c);
        while (l <= r) {
            int temp = l * l + r * r;
            if (temp < c) l++;
            else if (temp > c) r--;
            else return true;
        }
        return false;
    }
}

　　

Reference:

https://leetcode.com/problems/sum-of-square-numbers/discuss/104930/Java-Two-Pointers-Solution