【原】LeetCode 633.平方数之和

LeetCode 633.平方数之和题目链接:

https:///problems/sum-of-square-numbers/

题目描述:

给定一个非负整数c，你要判断是否存在两个整数a 和 b，使得 a²+ b² = 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

提示：

0 <= c <= 2³¹ - 1

题目分析:

看到此题，我们还是不禁会想到使用双指针进行求解。首先分析一下这两个数a，b要在什么范围内才有可能符合条件a²+ b² = c？这两个数都可以为任意非负整数，假设一个数a取值为0，那我们就只需考虑 b² = c，b的取值最大只能是根号c，通过分析我们可以得到两个数应该取的初始值，即一个数初始化为0，另一个数初始化为根号c。我们假定a小于等于b，计算a²+ b² 的值，并与目标值c进行比较，如果刚好相等，则符合题意返回true即可。但当和小于目标值c，说明和过小，我们需要适当增加两个数中的某个数，使其和增大，如果选择右值，则会增加过大，所以我们应该选择对左值进行增加。反过来如果和小于目标值c，我们同样应该选择对右值进行修改，使右值减小。

题解:

执行用时: 4 ms

内存消耗: 35.1 MB

class Solution {    public boolean judgeSquareSum(int c) {        // 定义左右元素的值        long l = 0, r = (long)Math.sqrt(c);        // 当左元素小于等于右元素时执行循环        while (l <= r) {            // 计算两数平方之和            long sum = l * l + r * r;            // 如果和刚好与目标值相等，则返回true            if (sum == c)                return true;            // 如果和小于目标值，说明左值过小，需要加大            if (sum < c)                ++l;            // 如果和大于目标值，说明右值过大，需要减小            if (sum > c)                --r;        }        // 如果左值大于右值，说明没有找到符合条件的数，返回false        return false;    }}

题目来源:力扣(LeetCode)