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:
1
Input: 5
2
3
Output: True
4
5
Explanation: 1 * 1 + 2 * 2 = 5
Copied!
Example 2:
1
Input: 3
2
3
Output: False
Copied!

2. Implementation

(1) Binary Search
1
class Solution {
2
public boolean judgeSquareSum(int c) {
3
for (long num = 0; num <= (long)Math.sqrt(c); num++) {
4
long target = c - num * num;
5
6
if (isSquareNum(0, target, target)) {
7
return true;
8
}
9
}
10
return false;
11
}
12
13
public boolean isSquareNum(long start, long end, long target) {
14
long mid = 0;
15
16
while (start <= end) {
17
mid = start + (end - start)/2;
18
19
if (mid * mid == target) {
20
return true;
21
}
22
else if (mid * mid < target) {
23
start = mid + 1;
24
}
25
else {
26
end = mid - 1;
27
}
28
}
29
return false;
30
}
31
}
Copied!

3. Time & Space Complexity

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