SumOfSquareNumbers2 [source code]

public class SumOfSquareNumbers2 {
static
/******************************************************************************/
public class Solution {
    public boolean judgeSquareSum(int c) {
        if (isSquare(c)) return true;
        int end = (int) Math.sqrt(c / 2);
        for (int i = 1; i <= end; i++) {
            if (isSquare(c - i * i)) return true;
        }
        return false;
    }

    public boolean isSquare(int n) {
        int root = (int) Math.sqrt(n);
        return root * root == n;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SumOfSquareNumbers2.Solution tester = new SumOfSquareNumbers2.Solution();
        int[] inputs = {
            5, 4, 3, 0, 2, 
        };
        for (int i : inputs) {
            System.out.println(i + " -> " + tester.judgeSquareSum(i));
        }
    }
}

更改了一下搜索的思路, 之前的思路搜索的其实是平方值, 这里我们搜索第一项的平方根, range 就可以缩小到平方根级别; 最后的速度是21(39), 还可以接受;

事实上, 这种平方的值的搜索的问题, 好像都是搜索平方根的值比搜索平方本身的值要少搜索很多;

这个是 editorial 上面一个类似的做法, 是解3:

public class Solution {  
    public boolean judgeSquareSum(int c) {  
        for (long a = 0; a * a <= c; a++) {  
            double b = Math.sqrt(c - a * a);  
            if (b == (int) b)  
                return true;  
        }  
        return false;  
    }  
}

就是把我的这些东西整合在一个循环;

解4是一个奇葩答案:

public class Solution {  
    public boolean judgeSquareSum(int c) {  
        for (long a = 0; a * a <= c; a++) {  
            int b = c - (int)(a * a);  
            if (binary_search(0, b, b))  
                return true;  
        }  
        return false;  
    }  
    public boolean binary_search(long s, long e, int n) {  
        if (s > e)  
            return false;  
        long mid = s + (e - s) / 2;  
        if (mid * mid == n)  
            return true;  
        if (mid * mid > n)  
            return binary_search(s, mid - 1, n);  
        return binary_search(mid + 1, e, n);  
    }  
}

并没有什么好东西在里面, 还是对第一个平方根进行 iterate, 然后第二个平方根用 Binary Search 来寻找 check; 为了方便他这里的 Binary Search 是用 recursion 写的;

discussion 上面有一个比较有意思的解法, 不依赖于isSquare的判断:

public class Solution {  
    public boolean judgeSquareSum(int c) {  
        if (c < 0) {  
            return false;  
        }  
        int left = 0, right = (int)Math.sqrt(c);  
        while (left <= right) {  
            int cur = left * left + right * right;  
            if (cur < c) {  
                left++;  
            } else if (cur > c) {  
                right--;  
            } else {  
                return true;  
            }  
        }  
        return false;  
    }  
}

我刚开始也是想到过用Binary Search 来做, 不过只用 Binary Search(或者说2pointers) 做过search for one的操作, 这里实际上要找的可以说是search for two?
还是不知道这个人的算法里面透露了他对于2pointers 怎么样的理解?

或者可以这样理解: 这个问题看起来是搜索两个平方根, 其实搜索的就是一个平方根: 如果 c是sum of square的话, 那么知道一个平方根, 其实另外一个平方根也就知道了;

不过这个算法好像也没有加速很多? 这个只是2pointers, 而不是一个 Binary Search, 所以并没有完成从O(N) 到O(lgN) 的转变; 至于搜索上限的缩短大部分算法都做得到;

另外我们以前说过, 如果看到sorted什么的, 还是很容易想到2pointers 的. 不过现在总结一下, 数论搜索的题目, 好像也很容易想到2pointers 上面去;

这个是 discussion 上面另外一个基于平方判断的解:

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

        for (int i = 0; i <= Math.sqrt(c); i++) {  
            set.add(i * i);  
            if (set.contains(c - i * i)) {  
                return true;  
            }  
        }  
        return false;  
    }  
}

这个解就是利用了对称性: 虽然只有 i 一个在走, 但是当 i 走过了半点之后, c - i i如果是平方, 那么其平方根就肯定是 i 已经走过的值, 那么i i肯定就在 set 里面;
注意他这里的上限是sqrt(c)而不是sqrt(c / 2);

Problem Description

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:
Input: 5
Output: True
Explanation: 1 1 + 2 2 = 5
Example 2:
Input: 3
Output: False
Difficulty:Easy
Total Accepted:5K
Total Submissions:15.9K
Contributor: Stomach_ache
Companies
linkedin
Related Topics
math
Similar Questions
Valid Perfect Square