633. Sum of Square Numbers

Medium

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

Constraints:

• 0 <= c <= 231 - 1

解題

Binary search 來解題，最右邊的值設定為 c 開根號。

Runtime: 0 ms, faster than 100%

Memory Usage: 1.9 MB, less than 34.88%

func judgeSquareSum(c int) bool {
    if c == 1 { return true }
    
    left := 0
    right := 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
}