[LeetCode] 633. Sum of Square Numbers

題：https://leetcode.com/problems/sum-of-square-numbers/submissions/1

題目

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
           

思路

題目大意

給定一個數 c，c求 是否存在a，b使得a2 + b2 = c

解題思路

參考 Two Sum。pleft 指針為 0，pright為可能的最大值。求其平方的和 與 c比較，并相應移動兩指針。

code

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