algorithm/leetcode/SumOfSquareNumbers.java at master · skyczhao/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package leetcode;

/**
 * SumOfSquareNumbers
 * https://leetcode-cn.com/problems/sum-of-square-numbers/
 * 633. 平方数之和
 * https://leetcode-cn.com/problems/sum-of-square-numbers/solution/shuang-zhi-zhen-by-oshdyr-5rbm/
 *
 * @since 2021-04-28
 */
public class SumOfSquareNumbers {
    public static void main(String[] args) {
        SumOfSquareNumbers sol = new SumOfSquareNumbers();
        System.out.println(sol.judgeSquareSum(5));
        System.out.println(sol.judgeSquareSum(4));
        System.out.println(sol.judgeSquareSum(3));
        System.out.println(sol.judgeSquareSum(2));
        System.out.println(sol.judgeSquareSum(1));
        System.out.println(sol.judgeSquareSum(10));
        System.out.println(sol.judgeSquareSum(11));
        System.out.println(sol.judgeSquareSum(12));
        System.out.println(sol.judgeSquareSum(290000000));
    }

    public boolean judgeSquareSum(int c) {
        int cRoot = (int) Math.sqrt(c);
        if (cRoot * cRoot == c) {
            return true;
        }

        int a = 1;
        int b = (int) Math.sqrt(c) + 1;
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum > c) {
                b--;
            } else if (sum < c) {
                a++;
            } else {
                return true;
            }
        }
        return false;
    }
}