原题

LintCode 697. Check Sum of Square Numbers

Description

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

Example

Given n = 5
Return true // 1 * 1 + 2 * 2 = 5

Given n = -5
Return false

代码

class Solution {
public:
    /*
     * @param : the given number
     * @return: whether whether there're two integers
     */
    bool checkSumOfSquareNumbers(int num) {
        // write your code here
        if (num < 0) return false;
        int right = floor(sqrt(num));
        if (right * right == num) return true;
        int left = 1;
        while (left < right) {
            int result = left * left + right * right;
            if (result == num) {
                return true;
            } else if (result > num) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
};