633. Sum of Square Numbers
1. Description
Given a non-negative integer c, decide whether there’re two integers a and b such that a2 + b2 = c.
2. Example
Example 1:
Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: c = 3
Output: false
3. Constraints
- 0 <= c <= 231−1
4. Solutions
Library
n = c
Time complexity: O(√n)
Space complexity: O(1)
class Solution {
public:
bool judgeSquareSum(int c) {
for (long i = 0, j = 0; i <= j; ++i) {
j = sqrt(c - i * i);
if (i * i + j * j == c) {
return true;
}
}
return false;
}
};
Two Pointers
n = c
Time complexity: O(√n)
Space complexity: O(1)
class Solution {
public:
bool judgeSquareSum(int c) {
for (long left = 0, right = sqrt(c); left <= right;) {
long multiply = left * left + right * right;
if (multiply == c) {
return true;
}
multiply < c ? ++left : --right;
}
return false;
}
};