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: 5Output: TrueExplanation: 1 * 1 + 2 * 2 = 5

 

Example 2:

Input: 3Output: False

 

算法：

1. 递增法。用一个不断++1的数来算出所有平方数并存到set里，如果到某个点你发现c-i^2已经存在过set里了，那就说明你成功找到了。 但是会TLE

2.双指针法。一个一开始指0，一个一开始指sqrt(n)，然后根据平方和决定指针怎么移。这个一开始已经和答案很逼近所以时间复杂度低很多。

3.确认互补数是不是整数法。很简洁。

细节：Math.sqrt返回的是double，注意人工转换。

 

实现1：

class Solution {    public boolean judgeSquareSum(int c) {        Set
     
       set = new HashSet<>();        int n = 0;        while (n * n <= c) {            set.add(n * n);            if (set.contains(c - n * n)) {                return true;            }            n++;        }        return false;    }}
     

实现2：

class Solution {    public boolean judgeSquareSum(int c) {        if (c < 0) {            return false;        }        int i = 0;        int j = (int) Math.sqrt(c);        while (i <= j) {            int ss = i * i + j * j;            if (ss == c) {                return true;            } else if (ss < c) {                i++;            } else {                j--;            }        }        return false;    }}

实现3：

class Solution {    public boolean judgeSquareSum(int c) {        for (int i = 0; i <= (int)Math.sqrt(c) + 1; i++) {            if (Math.floor(Math.sqrt(c - i * i)) == Math.sqrt(c - i * i) ) {                return true;            }        }        return false;    }}