leetcode-633-Sum-of-Square-Numbers

发表于   |  

描述

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

1
2
3
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

1
2
Input: 3
Output: False

分析

判断一个数是否为两个平方数之和。夹逼法，嗯。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0, b = (int) Math.sqrt(c);
        while (a <= b) {
            if (a*a + b*b == c) {
                return true;
            } else if (a*a + b*b < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
}

解决方案是2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func judgeSquareSum(c int) bool {
    left, right := 0, int(math.Sqrt(float64(c)))
    
    for left <= right {
        sum := left * left + right * right
        if sum == c {
            return true
        } else if sum > c {
            right--
        } else {
            left++
        }
    }
    return false
}

相关问题

题目来源