平方数之和
2020-05-27 本文已影响0人
WAI_f
题目:
给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c。
示例:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5。
解题方法:
这道题我真的犹豫了,一时间不知道怎么做,后来就忍不住看了一下题解,思路就是双指针。我就按照这个思路做了一下,但是在实际编程的时候,遇到两个问题:
- 双指针的调整:当i*i + j*j != c时,i与j怎么变化,后来想想每次都只调整一个指针才可以获得正确结果,也可以从最开始的状态一步步推导。
- long和int的区别:使用int的时候提示溢出,查看题解用的是long,我改成Long以后果然通过了。在网上查找资料,有博客提到在x64上long是64bit的,但是int还是32bit的,那么leetcode上的测试环境应该是x64的。
代码和结果:
class Solution {
public:
bool judgeSquareSum(int c) {
long i=0;
long j=(int)sqrt(c);
int flag=false;
while(i<=j)
{
if(i*i+j*j==c)
{
flag=true;
break;
}
else if(i*i+j*j>c)
{
j--;
}
else
{
i++;
}
}
return flag;
}
};
运行结果:
原题链接:https://leetcode-cn.com/problems/sum-of-square-numbers/