633. Sum of Square Numbers (Easy)

Leetcode / 力扣
题目描述：判断一个非负整数是否为两个整数的平方和。

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

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

示例2:

输入: 3
输出: False

方法一：使用 sqrt 函数

 /**
     * 使用 sqrt 函数
     * @param c
     * @return
     */
    public boolean judgeSquareSum4(int c){
        for (int a = 0;a*a < c;a++){
            double b = Math.sqrt(c - a*a);
            if (b == (int)b){
                return true;
            }
        }
        return false;
    }

方法一：二分查找

 public boolean judgeSquareSum(int c) {
        // 根据条件，有 b = c- a*a
        //循环迭代a，因为 (a*a) 所以只需要找出 b 能否开方出正整数
        for (long a = 0; a * a <= c; a++) {
            int b = c - (int)(a * a);
            //二分法查找b能否开方出正整数
            if (binary_search(0, b, b)) {
                return true;
            }
        }
        return false;
    }
    //双指针 左指针从0开始，
    public boolean binary_search(long s, long e, int n) {
        //如果 左指针大于右指针证明n无正整数方根
        if (s > e) {
            return false;
        }
        //查找指针中间值
        long mid = s + (e - s) / 2;
        //如果min *min = n ，则 n 的开方等于 min，返回ture
        if (mid * mid == n){
            return true;
        }
        //如果mid * mid > n，则移动左指针（减小中间值），再次二分法找中间值的，计算min是否是n的二元平方根
        if (mid * mid > n){
            return binary_search(s, mid - 1, n);
        }
    //如果mid * mid < n，则移动右指针（增大中间值），再次二分法找中间值的，计算是min否是n的二元平方根
        return binary_search(mid + 1, e, n);
    }