leetcode 633. Sum of Square Numbers
这是一道easy题，但是在leetcode solution那里提供了很多种解法。这道题目其实很多解法都比较偏重数学知识，就是得到的结论需要数学推理。我不擅长数学，所以自己写的时候偏向于写比较直接的东西，不需要靠数学公式/理论的那种。
还有就是这道题目比较tricky的地方是，必须注意int的值的范围。take my solution as example.
solution: two pointers
class Solution {
public boolean judgeSquareSum(int c) {
long left =0, right = (int)Math.sqrt(c);
while(left<=right) {
long sum = left*left + right*right;
if(sum == c) {
return true;
} else if(sum < c) {
left++;
} else {
right --;
}
}
return false;
}
}
here left is long type, because when we have left*left + right*right, the result might be larger than the max value of integer in java, one can test using 2147483600. if we have left in int type, we must force change the result of (left*left) to long, so that the result of the sum can be long too.
time complexity: O(sqrt(c)), iterate once
space complexity: O(1) constant space
网友评论