- Sum of Square Numbers (Easy)
Leetcode / 力扣
题目描述：判断一个非负整数是否为两个整数的平方和。
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False
方法一：使用 sqrt 函数
/**
* 使用 sqrt 函数
* @param c
* @return
*/
public boolean judgeSquareSum4(int c){
for (int a = 0;a*a < c;a++){
double b = Math.sqrt(c - a*a);
if (b == (int)b){
return true;
}
}
return false;
}
方法一：二分查找
public boolean judgeSquareSum(int c) {
// 根据条件，有 b = c- a*a
//循环迭代a，因为 (a*a) 所以只需要找出 b 能否开方出正整数
for (long a = 0; a * a <= c; a++) {
int b = c - (int)(a * a);
//二分法查找b能否开方出正整数
if (binary_search(0, b, b)) {
return true;
}
}
return false;
}
//双指针 左指针从0开始，
public boolean binary_search(long s, long e, int n) {
//如果 左指针大于右指针证明n无正整数方根
if (s > e) {
return false;
}
//查找指针中间值
long mid = s + (e - s) / 2;
//如果min *min = n ，则 n 的开方等于 min，返回ture
if (mid * mid == n){
return true;
}
//如果mid * mid > n，则移动左指针（减小中间值），再次二分法找中间值的，计算min是否是n的二元平方根
if (mid * mid > n){
return binary_search(s, mid - 1, n);
}
//如果mid * mid < n，则移动右指针（增大中间值），再次二分法找中间值的，计算是min否是n的二元平方根
return binary_search(mid + 1, e, n);
}
