Leetcode 633：平方数之和

题目描述

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

示例1:

输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5

 

示例2:

输入: 3 输出: False

 

解题思路

（1）双指针

class Solution { public: bool judgeSquareSum(int c) { long r = sqrt(c); long l = 0; while(l <= r){ long tmp = l*l+r*r; if(tmp == c) return true; else if(tmp > c) --r; else ++l; } return false; } };

（2）折半查找

class Solution { public: bool judgeSquareSum(int c) { int t = sqrt(c); for(int i=0;i<=t;++i){ int fid = c - i*i; int l = 0,r = i; while(l <= r){ int mid = l + (r-l) / 2; int tmp = mid*mid; if(tmp == fid) return true; else if(tmp > fid) r = mid-1; else l = mid+1; } } return false; } };