LeetCode 633. Sum of Square Numbers

Description

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

Analysis

这道题不需要很复杂的数论知识，纯暴力也可以过，但两层循环遍历可能的数字会TLE，要利用

a

,

b

两数之间的关系，一层循环即可，直接利用sqrt()函数和强制类型转换即可AC。

Code

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = ; a * a <= c; a++){
            double b = sqrt(c - a * a);
            if ((int)b == b)
                return true;            
        }
        return false;
    }
};
           

Appendix

• Link: https://leetcode.com/problems/sum-of-square-numbers/
• Run Time: 13ms