题目描述

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

样例1

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

样例2

输入：c = 3
输出：false

样例3

输入：c = 4
输出：true

样例4

输入：c = 2
输出：true

提示

• 0 <= c <= 2^31 - 1

算法1

(枚举) $\mathcal O(\sqrt{c})$

• a和b的范围都是[0, $\sqrt{c}$]，枚举所有a，根据$b = \sqrt{c - a^2}$计算出b，然后进行判断即可

Java 代码

class Solution {
    public boolean judgeSquareSum(int c) {
        int maxv = (int)Math.sqrt(c);
        for(int a = 0; a <= maxv; a++){
            int b = (int)Math.sqrt(c - a * a);
            if(a * a + b * b == c) return true;
        }
        return false;
    }
}

算法2

(双指针) $\mathcal O(\sqrt{c})$

• 根据a和b的范围，可以确定如果存在答案，答案一定满足a和b都是[$0, \sqrt{c}$]中的整数
• 定义两个指针，一个从$0$开始，一个从$\sqrt{c}$开始
  1. 如果$a^2 + b^2 < c$，则a++
  2. 如果$a^2 + b^2 > c$，则b--
  3. 如果找到答案，则退出循环
• 证明：https://leetcode-cn.com/problems/sum-of-square-numbers/solution/shuang-zhi-zhen-de-ben-zhi-er-wei-ju-zhe-ebn3/

Java代码

class Solution {
    public boolean judgeSquareSum(int c) {
        int maxv = (int)Math.sqrt(c);
        int a = 0, b = maxv;
        while(a <= b){
            if(a * a + b * b < c){
                a++;
            }else if(a * a + b * b > c){
                b--;
            }else{
                return true;
            }
        }
        return false;
    }
}