633. Sum of Square Numbers

Description

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Examples

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Constraints:

0 <= c <= 231 - 1

C++

由於是兩個 int 去查找是否符合目標。所以先建立一個 vector 存放所有平方

$0^2+1^2+2^2+...+n^2$，然後迴圈遍歷這個　vector 去判斷 c - vector[i] 是否為整數。

class Solution {
public:
    bool isSRT(double value) {
        double root = sqrt(value);
        return floor(root) == root;
    }
    bool judgeSquareSum(int c) {
        unsigned int tmp = sqrt(c);
        vector<unsigned int> nums(tmp + 1);
        for (int i = 0; i <= tmp; i++) {
            nums[i] = i * i;
        }

        for (int i = 0; i <= tmp; i++) {
            if (isSRT(c - nums[i])) {
                return true;
            }
        }

        return false;
    }
};

這方法相對較慢也需要很多空間，使用 left, right 去查找，其他人的方法：

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long left = 0, right = sqrt(c);

        while (left <= right) {
            const long long sum = left * left + right * right;

            if (sum == c)
                return true;

            if (sum > c)
                --right;
            else
                ++left;
        }

        return false;
    }
};