Sum of Square Numbers

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

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a^2 + b^2 = c.

Thoughts

和2sum很像, l从0开始, r从最大的可能值sqrt(N)开始, 如果l + r < N, 那么再小的r-1等只会更小; 同理l+r>N时, 更大的l只会让和更大. 注意结束条件是l == r, 因为可以有类似1 + 1 = 2.

Code

class Solution {
    public boolean judgeSquareSum(int c) {
        if (c < 0) {
            return false;
        }

        int l = 0, r = (int)Math.sqrt(c);
        while (l <= r) {
            int cur = (int)Math.pow(l, 2) + (int)Math.pow(r, 2);
            if (cur < c) {
                l++;
            } else if (cur > c) {
                r--;
            } else {
                return true;
            }
        }

        return false;
    }
}

Analysis

时间复杂度O(sqrt(N)). 空间O(1).