[leetcode #633] Sum of Square Numbers

Problem

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 <= 2³¹ - 1

Idea

これは、与えられた数cが任意の2つの数のそれぞれの平方の値の和に等しいか否かを決定する問題である.ひらめいた考えがないので、直感的に質問に答えたい.まず、所与の数cの平方根を求め、その後、その数より小さいすべての整数の平方根をsetに加算する.その後のsetで各整数にナビゲートすると、c-(setの整数)値がsetに含まれているかどうかが再びナビゲートされます.ある場合はtrueを返し、ループが完了するとfalseを返します.
アルゴリズム#アルゴリズム#

HashSetを製造します.

c平方根未満の整数(>=0)について、ループ二乗の数をセットに加算します.

セットの整数をナビゲートし、(c-i)値がセットに含まれているかどうかを決定します.
a.含まれている場合はtrueを返します.
b.含まなければ、再探求します.

セットのすべての数字が検索されたがtrueが返されなかった場合、falseが返されます.

Solution

class Solution {
    public boolean judgeSquareSum(int c) {
        Set<Integer> set = new HashSet<Integer>();

        for (int i=0; i <= (int) Math.sqrt(c); i++) {
            set.add(i*i);
        }

        for (int i : set) {
            if (set.contains(c-i))
                return true;
        }

        return false;
    }
}

何の考えもないせいか、結果は最悪だった.ソリューションから見ると,バイナリ検索で解決する方法があり,setを用いる方法よりも賢明な方法であるようだ.バイナリ検索に慣れるのはいつですか...

Reference

https://leetcode.com/problems/sum-of-square-numbers/