1.题目

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

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

示例 2：
输入：c = 3
输出：false

提示：
0 <= c <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-square-numbers

2.思路

（1）暴力穷举法
比较容易想到的方法是，在区间 [0, $\sqrt{c}$ ] 内使用两层 for 循环进行穷举，看能否找出整数 a、b，使得 a² + b² = c。但是本题中 c 的取值范围为 [0, 2³¹ - 1] ，在 LeetCode 上提交时会出现“超出时间限制的提示”！所以显然该方法还有该进的空间。

（2）Math.sqrt()
为了节省枚举时间，我们可以在枚举 a 的过程中，使用 Math.sqrt(c - a * a) 来寻找 b，然后再判断 (int) b == b，如果相等，则说明 a² + b² = c，直接返回 true 即可；否则继续枚举，如果枚举结束后仍未找到，则返回 false。在枚举 a 的过程中需要注意：由于 a * a 的结果可能会 int 表示的范围，所以 a 的类型应该为 long；

（3）双指针
分析题目可知，现在要从区间 [0, $\sqrt{c}$ ] 中找出两个整数 a、b，使得 a² + b² = c，所以我们可以使用双指针来简化枚举过程：
① 定义两个指针 left、right，分别指向区间的左右端点；
② 开始遍历，先保存当前 sum = left * left + right * right，然后再进行判断：
如果 sum == c，找到了 a、b，直接返回 true 即可；
如果 sum < c，则 left- -；
如果 sum > c，则 right++；
③ 当 left > right 时，遍历结束，若此时还未找到，则返回 false。

3.代码实现（Java）

//思路1————暴力穷举法（超出时间限制）
class Solution {
    public boolean judgeSquareSum(int c) {
        int left = 0;
        int right = (int)Math.sqrt(c);
        for (int i = left; i <= right; i++) {
            if ((long)(i * i) + (long)(right * right) < c) {
                continue;
            }
            for (int j = i; j <= right; j++) {
                long res = (long)(i * i) + (long)(j * j);
                if (res == c) {
                    return true;
                }
                if (res > c) {
                    break;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//思路2————Math.sqrt()
class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            //在枚举 a 的同时，使用 Math.sqrt(c - a * a) 来寻找 b
            double b = Math.sqrt(c - a * a);
            /*
                如果 (int) b == b，则说明 (int) b 在类型转换中没有精度损失
                所以 a * a + b * b = c，即找到符合条件的 a、b
            */
            if ((int) b == b) {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//思路2————双指针
class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18