leetcode#633-平方数之和

考虑两个int相乘溢出问题

题目描述

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

示例 1：

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

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

输入：c = 4
输出：true

思路

其实就是从0~c之间，找出两个数的平方和等于c，为了再次缩短找的距离，先对c进行开方运算，再从0~sqrt(c)之间找出两个合适的值，和之前的两数之和一样，两个指针，一个从后往前，一个从前往后。

如果：sum = a^2 + b^2

• sum == c， return true
• sum > c， b–
• sum < c，a++

到现在，题目还没完，当c特别大（2147483600）的时候，从0~sqrt(c)计算sum的过程中，两个int相乘，得出的结果值大于int的范围时会溢出，导致找不到正确答案，所以两个指针a和b需要定义为long型

代码

Java

public boolean judgeSquareSum(int c) {
        long a = 0;
        long b = (long) Math.sqrt(c);
        while (a <= b) {
            if (a * a + b * b == c) {
                return true;
            } else if (a * a + b * b < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }