633.Sum of Square Numbers
原题
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
解决
暴力法
两个数，第一个从1到目标数的根号，第二个数从第一个数到目标数的根号，两层循环查找是否满足。 leetcode最后给出的结果是超时。
class Solution {
public boolean judgeSquareSum(int c) {
int maxNum = (int)Math.sqrt(c);
for(int i = 0; i <= maxNum; i ++) {
for(int j = i; j <= maxNum; j ++) {
int squ = i * i + j * j;
if(squ == c)
return true;
}
}
return false;
}
}
双指针
两个数，一个数从小到大，第二个数从最大值到小。两个数相遇后还不符合，则不满足。相加时，如果偏大，则大数减小；偏小则小数增大。
class Solution {
public boolean judgeSquareSum(int c) {
int i = 0, j = (int) Math.sqrt(c);
while(i <= j) {
int sum = i * i + j * j;
if(sum == c) {
return true;
} else if(sum < c) {
i ++;
} else {
j --;
}
}
return false;
}
}