给定一个非负整数 c , 你要判断是否存在两个整数 a 和 b, 使得 a2 + b2 = c.
示例 1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例 2:
输入: 3
输出: False
在这题里面, 可以使用二分查找来缩小搜索的范围
由数学定理 (我忘了具体的哪个定义) 可知, a 和 b 的具体取值范围落在 0 到根号 c 之间. 然后简单运用二分法就能十分便捷找到答案了.
代码如下:
- class Solution {
- public:
- bool judgeSquareSum(int c) {
- int l = 0;
- int r = floor(sqrt(c));
- while(l<r)
- {
- if ((l*l)>(c-(r*r)))
- r--;
- else if ((l*l)<(c-(r*r)))
- l++;
- else
- return true;
- }
- return false;
- }
- };
来源: http://www.bubuko.com/infodetail-3044772.html