Medium

题目描述

给定一个非负整数 c，你要判断是否存在两个整数 a 和 b，使得 a² + b² = c。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

提示：

  • 0 <= c <= 2³¹ - 1

解题思路

这道题要求判断一个数能否表示为两个平方数之和，有三种主要解法：

方法一：双指针（推荐） 设置两个指针 left = 0，right = sqrt(c)。计算 left² + right²：

  • 如果等于 c，返回 true
  • 如果小于 c，说明需要更大的数，left++
  • 如果大于 c，说明需要更小的数，right--

这种方法时间复杂度低且易于理解。

方法二：枚举 + 平方根判断 枚举 a 从 0 到 sqrt(c)，对于每个 a，计算 b² = c - a²，然后判断 b 是否为完全平方数。

方法三：费马平方和定理 根据费马定理，一个数能表示为两个平方数之和当且仅当该数的所有形如 4k+3 的质因数的指数都是偶数。但实现较复杂。

双指针法实现简单且效率高，是最优选择。

代码实现

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long left = 0, right = sqrt(c);
        
        while (left <= right) {
            long long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                left++;
            } else {
                right--;
            }
        }
        
        return false;
    }
};

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        left, right = 0, int(c**0.5)
        
        while left <= right:
            sum_val = left * left + right * right
            if sum_val == c:
                return True
            elif sum_val < c:
                left += 1
            else:
                right -= 1
        
        return False

public class Solution {
    public bool JudgeSquareSum(int c) {
        long left = 0, right = (long)Math.Sqrt(c);
        
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                left++;
            } else {
                right--;
            }
        }
        
        return false;
    }
}

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    let left = 0;
    let right = Math.floor(Math.sqrt(c));
    
    while (left <= right) {
        let sum = left * left + right * right;
        if (sum === c) {
            return true;
        } else if (sum < c) {
            left++;
        } else {
            right--;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针法
时间复杂度O(√c)
空间复杂度O(1)

相关题目