平方数之和

发表于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，633. 平方数之和

先看题目描述

gP0VGn.png

算法和思路

使用 sqrt 函数

从 0 到 $\sqrt{c}$ 枚举 a，利用 sqrt 函数求出对应的 b，若 b 是整数，则找到了一对满足条件的 a 和 b，直接返回 true；若到最后也没有找到满足条件的 b，则返回 false

双指针

初始化指针 a 等于 0，指针 b 等于 $\sqrt{c}$ ，进行如下操作：

  • 若 $a^2 + b^2 = c$，则找到了一对满足条件的 a 和 b，直接返回 true 即可
  • 若 $a^2 + b^2 < c$，则将 a 加 1
  • 若 $a^2 + b^2 > c$，则将 b 减 1

当 a > b 时结束查找，若到最后也没找到一对满足条件的 a 和 b，则返回 false

算法源码

使用 sqrt 函数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean judgeSquareSum(int c) {
        int max = (int)Math.sqrt(c / 2);
        for (int a = 0; a <= max; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0;
        int b = (int)Math.sqrt(c);
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum == c) {
                return true;
            }else if (sum < c) {
                a++;
            }else {
                b--;
            }
        }
        return false;
    }
}