这道题一开始用O(N2)的方法，结果发现有一个Integer.MAX_VALUE的input, 过不了；一般来说10^6- 10^7之后的要做到O(N)
image.png
直接用two pointers两头走，注意right pointer只需要到Math.sqrt(n), 不需要到n. 这样只需要O(N)
class Solution {
public boolean judgeSquareSum(int c) {
//a,b should be non-negative
int i = 0;
int j = (int) Math.sqrt(c);
while (i <= j){
int squareSum = i*i + j*j;
if (squareSum == c){
return true;
} else if (squareSum > c){
j--;
} else {
i++;
}
}
return false;
}
}
