633.平方数之和

目标

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

示例 1：

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

示例 2：

输入：c = 3
输出：false

说明：

• 0 <= c <= 2^31 - 1

思路

判断给定的整数是否是两个整数的平方和。

我们可以先从 0 开始计算每一个整数的平方和，直到平方和小于 Integer.MAX_VALUE, 不超过 10^5 个，将它保存到集合中，这一部分计算可以预处理。

然后我们还是同样的方法计算平方和 square，然后判断 c - square 是否在集合中，直到 square > c。

代码

/**
 * @date 2024-11-04 0:17
 */
public class JudgeSquareSum633 {

    public static Set<Integer> set = new HashSet<>(100000);

    static {
        long i = 0;
        long square = 0;
        while (true) {
            square = i * i;
            if (square > Integer.MAX_VALUE) {
                break;
            }
            set.add((int) square);
            i++;
        }
    }

    public boolean judgeSquareSum(int c) {
        long i = 0;
        long square = 0;
        while (true) {
            square = i * i;
            if (square > c) {
                break;
            } else if (set.contains((int) (c - square))) {
                return true;
            }
            i++;
        }
        return false;
    }

}

性能