[刷题防痴呆] 0633 - 平方数之和 (Sum of Squ

题目地址

https://leetcode.com/problems/sum-of-square-numbers/

题目描述

633. Sum of Square Numbers

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

 

Example 1:

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

Input: c = 3
Output: false
Example 3:

Input: c = 4
Output: true
Example 4:

Input: c = 2
Output: true
Example 5:

Input: c = 1
Output: true

思路

• two sum的变种.

关键点

• 由于本身可以计算 a * a + a * a = c. 因此先把数加入set再判断.

代码

• 语言支持：Java

class Solution {
    public boolean judgeSquareSum(int c) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i <= Math.sqrt(c); i++) {
            int num = i * i;
            set.add(num);            
            if (set.contains(c - num)) {
                return true;
            }
        }

        return false;
    }
}