LeetCode 633、平方数之和

1）题目描述

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

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

提示：

• 0 <= c <= 231 - 1

2）分析

双指针。两个指针i, j分别从0和sqrt(c)出发，在i

• i*i+j*j==c，返回true；
• i*i+j*j
• i*i+j*j>c，j--。

注意，在判断i*i+j*j与c的关系的时候，应该写成i*i==c-j*j，i*ic-j*j，避免溢出。

3）C++代码

class Solution {
public:
    bool judgeSquareSum(int c) {
       int i=0,j=(int)sqrt(c);
       while(i<=j){
           if(i*i==c-j*j)
                return true;
            else if(i*i>c-j*j)
                j--;
            else
                i++;
       }
       return false;
    }
};