@@ -0,0 +1,1478 @@
+package array;%0A%0Aimport java.util.HashSet;%0Aimport java.util.Set;%0A%0Apublic class SumOfSquareNumbers %7B%0A%0A    //TAG: LinkedIn%0A    //TAG: math%0A    //TAG: array%0A    //Difficulty: Easy%0A%0A    /**%0A     * 633. Sum of Square Numbers%0A     * Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.%0A%0A     Example 1:%0A     Input: 5%0A     Output: True%0A     Explanation: 1 * 1 + 2 * 2 = 5%0A     Example 2:%0A     Input: 3%0A     Output: False%0A     */%0A%0A    /**%0A     * Solution 1:%0A     * left from 0 to right, right from n - 1 to left, if left%5E2 + right%5E2 %3C c, left++, otherwise right--%0A     *%0A     * Time: O(c)%0A     * Space: O(1)%0A     */%0A%0A    public boolean judgeSquareSum(int c) %7B%0A        int l = 0, r = c;%0A        while (l %3C r) %7B%0A            int num = l * l + r * r;%0A            if (num == c) return true;%0A            else if (num %3C c) l++;%0A            else r--;%0A        %7D%0A        return false;%0A    %7D%0A%0A    /**%0A     * Solution 2:%0A     * similar to two sum%0A     *%0A     * since above l will not exceed sqrt(c) and r will not smaller than sqrt(c)%0A     * so loop from 0 to sqrt(c), and check if hashSet contains c - l * l%0A     *%0A     * Time: O(sqrt(c))%0A     * Space: O(sqrt(c))%0A     */%0A%0A    public boolean judgeSquareSum2(int c) %7B%0A        Set%3CInteger%3E set = new HashSet%3C%3E();%0A        for (int i = 0; i %3C= Math.sqrt(c); i++) %7B%0A            set.add(i * i);%0A            if (set.contains(c - i * i)) return true;%0A        %7D%0A        return false;%0A    %7D%0A%0A%0A%7D%0A

633. Sum of Square Numbers