Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a^2 + b^2 = c.
Thoughts
和2sum很像, l从0开始, r从最大的可能值sqrt(N)开始, 如果l + r < N, 那么再小的r-1等只会更小; 同理l+r>N时, 更大的l只会让和更大. 注意结束条件是l == r, 因为可以有类似1 + 1 = 2.
Code
class Solution {
public boolean judgeSquareSum(int c) {
if (c < 0) {
return false;
}
int l = 0, r = (int)Math.sqrt(c);
while (l <= r) {
int cur = (int)Math.pow(l, 2) + (int)Math.pow(r, 2);
if (cur < c) {
l++;
} else if (cur > c) {
r--;
} else {
return true;
}
}
return false;
}
}