平方数之和Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

提示：

0 <= c <= 2³¹ - 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

# 总结

分析出几种情况，然后分别对各个情况实现