「力扣」第 633 题：平方数之和（中等）

双指针：https://blog.csdn.net/qq_34595352/article/details/93202536

https://blog.csdn.net/Ding_xiaofei/article/details/81704470

• 题目链接 (opens new window)

方法一：二分查找

分析

题目要求我们找到是否存在两个整数 和 ，使得 ，该表达式有 2 个变量 和 不确定，我们可以枚举其中一个变量 ，此时 ，为了确定 的值，可以使用二分查找，请见 69. x 的平方根。

值得注意的是，在编码的过程中，会使用到「平方」运算，根据题目中给出的提示 ，相关变量需要声明成 长整型，否则会出现溢出。

代码

public class Solution {

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

        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;
    }
}

复杂度分析

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

• 空间复杂度：。

方法三：

根据 Sum of two squares theorem (opens new window)：

public class Solution {

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

        for (int base = 2; base <= Math.sqrt(c); base++) {
            if (c % base != 0) {
                continue;
            }
            int exp = 0;
            while (c % base == 0) {
                c /= base;
                exp++;
            }

            // 根据 Sum of two squares theorem 验证
            if (base % 4 == 3 && exp % 2 != 0) {
                return false;
            }
        }

        // System.out.println(c);
        // 最后剩下的数的幂次一定为 1

        if (c == 1) {
            return true;
        }
        return c % 4 == 1;
    }
}