平方数之和Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
示例 2：
输入：c = 3
输出：false
提示：
- 0 <= c <= 231 - 1
# 思路
// 如果存在符合条件的a，b，那么a和b一定在0和sqrt(c)之间。
// 最朴素的思路，两层for循环，从0到sqrt(c)，看是否存在符合条件的a和b。相当于遍历了两次从0到sqrt(c)
// 显然，没有双指针快捷，双指针只需要遍历一次即可。**为什么使用双指针不会把正确答案排除在外呢**。我认为这才是需要认真考虑的问题，而不是双指针直接用。我们用a表示第一个数，b表示第二个数。从初始开始考虑，a = 0，b = (int)Math.sqrt(c)
// if(a*a+b*b<c)，那么显然，a固定的情况下和无论如何变化b值都不会满足当前的条件，由此，**a=0一定不在正确答案中**，所以可以直接排除。
// 反之，if(a*a+b*b>c)，b固定的情况下，当前所有能变化的a值，都不会满足条件，因此，**当前的b也一定不在正确答案中**。
// 综上，双指针法确保正确答案不会被排除。
# 解法
class Solution {
// 如果存在符合条件的a，b，那么a和b一定在0和sqrt(c)之间。
// 最朴素的思路，两层for循环，从0到sqrt(c)，看是否存在符合条件的a和b。相当于遍历了两次从0到sqrt(c)
// 显然，没有双指针快捷，双指针只需要遍历一次即可。**为什么使用双指针不会把正确答案排除在外呢**。我认为这才是需要认真考虑的问题，而不是双指针直接用。我们用a表示第一个数，b表示第二个数。从初始开始考虑，a = 0，b = (int)Math.sqrt(c)
// if(a*a+b*b<c)，那么显然，a固定的情况下和无论如何变化b值都不会满足当前的条件，由此，**a=0一定不在正确答案中**，所以可以直接排除。
// 反之，if(a*a+b*b>c)，b固定的情况下，当前所有能变化的a值，都不会满足条件，因此，**当前的b也一定不在正确答案中**。
// 综上，双指针法确保正确答案不会被排除。
public boolean judgeSquareSum(int c) {
long a = 0;
long b = (long)Math.sqrt(c);
while(a <= b){
if(a*a+b*b<c){
a++;
}else if(a*a+b*b>c){
b--;
}else{
return true;
}
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 总结
- 分析出几种情况，然后分别对各个情况实现
