README_EN.md

633. Sum of Square Numbers

中文文档

Description

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

 

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Example 3:

Input: c = 4
Output: true

Example 4:

Input: c = 2
Output: true

Example 5:

Input: c = 1
Output: true

 

Constraints:

• 0 <= c <= 231 - 1

Solutions

The picture above shows the relationship between a, b, and c. This question is actually looking up c in this table

From the upper right corner of the table, it is not difficult to find that it is similar to a binary search tree, so just start from the upper right corner and search according to the law of the binary search tree

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;
    }
}

...