「力扣」第 633 题：平方数之和（简单）

• 题目链接：633. 平方数之和 (opens new window)。

说明：本题我参与了编写官方题解，所以内容和官方题解有重合的部分。

题目描述

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

示例 1：

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

示例 2：

输入：c = 3
输出：false

示例 3：

输入：c = 4
输出：true

示例 4：

输入：c = 2
输出：true

示例 5：

输入：c = 1
输出：true

提示：

方法一：暴力解法

由于 、 均为整数，并且 。可以枚举 和 所有可能的情况，时间复杂度为 。但有一些情况没有必要讨论。例如：当 时，当 的时候，枚举 的时候，只需要枚举到 就可以结束了，这是因为 。当 时，一定有 。

注意到这一点，可以使用「双指针」或者「二分查找」降低时间复杂度。

方法二：双指针

不失一般性，可以假设 ，初始时 ，。

• 如果 ，我们找到了题目要求的一个解，返回 true；
• 如果 ，此时需要将 ，继续搜索；
• 如果 ，此时需要将 ，继续搜索。

直到 。

参考代码 1：

public class Solution {
    public boolean judgeSquareSum(int c) {
        if (c == 0 || c == 1 || c == 2) {
            return true;
        }

        int left = 0;
        int right = (int) Math.sqrt(c);
        while (left <= right) {
            int sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
}

复杂度分析：

• 时间复杂度：，最差情况下 和 一共枚举了 里的所有整数；

• 空间复杂度：。

方法三：二分查找

和 是两个待定的整数，我们可以枚举 的值，通过二分查找的方式确定 的值，可以参考 69. x 的平方根。

需要注意的是：本题 的取值范围在 。不同的编程语言声明的变量，以及在计算的过程中可能会发生的整型溢出的情况。

参考代码 2：

public class Solution {

    public boolean judgeSquareSum(int c) {
        if (c == 0 || c == 1 || c == 2) {
            return true;
        }

        // 固定 a ，问题转化为找是否存在一个整数的平方等于 b
        for (long a = 0; a * a <= c; a++) {
            long bSquare = c - a * a;

            long left = 0;
            long right = bSquare;
            while (left <= right) {
                long mid = left + (right - left) / 2;
                if (mid * mid == bSquare) {
                    return true;
                } else if (mid * mid < bSquare) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：，其中枚举 的时间复杂度为 ，二分查找的时间复杂度为 ；
• 空间复杂度：。

---

作者：liweiwei1419 链接：https://suanfa8.com/two-pointers/solutions-3/0633-sum-of-square-numbers 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。