> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/two_sum/sum-of-square-numbers.md).

# 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).