[LeetCode] 633. Sum of Square Numbers

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

平方数之和。

给定一个数字C，请判断是否存在另外两个数字A和B，满足A平方 + B平方 = C平方。

思路是二分法。根据题意，A和B的范围一定比C的平方根要小，所以二分的范围是0 - Math.sqrt(C)。可以将 left = 0，right = Math.sqrt(C) 做二分，其余部分就是二分法题目的常规判断了。

时间O(logn)

空间O(1)

Java实现

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

LeetCode 题目总结