LeetCode 633. 平方数之和-爱代码爱编程
633. 平方数之和
给定一个非负整数 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
题解
右指针的初始化,实现剪枝,从而降低时间复杂度。设右指针为 x,左指针固定为 0,为了使 x的值尽可能接近 target,我们可以将 x 取为 sqrt(target)。
因为最多只需要遍历一次 0~sqrt(target),所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量,因此空间复杂度为 O(1)。
代码
class Solution {
public:
bool judgeSquareSum(int c) {
long l=0,r=sqrt(c);
int sum=0;
while(l<=r)
{
sum=l*l+r*r;
if(sum==c)
return true;
else if(sum>c)
r--;
else
l++;
}
return false;
}
};