README.md

633. 平方数之和

English Version

题目描述

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

 

示例 1：

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

示例 2：

输入：c = 3
输出：false

示例 3：

输入：c = 4
输出：true

示例 4：

输入：c = 2
输出：true

示例 5：

输入：c = 1
输出：true

 

提示：

• 0 <= c <= 231 - 1

解法

上图为 a，b，c 之间的关系，这题其实就是在这张“表”里查找 c

从表的右上角看，不难发现它类似一棵二叉查找树，所以只需从右上角开始，按照二叉查找树的规律进行搜索

Python3

class Solution(object):
    def judgeSquareSum(self, c):
        i, j = 0, int(math.sqrt(c))
        while i <= j:
            s = i * i + j * j
            if s < c:
                i += 1
            elif s > c:
                j -= 1
            else:
                return True
        return False

Java

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

...