0633-平方数之和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

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

示例 1：

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

示例 2：

**输入：** c = 3
**输出：** false

提示：

  • 0 <= c <= 231 - 1

前言

对于给定的非负整数 c，需要判断是否存在整数 a 和 b，使得 a^2 + b^2 = c。可以枚举 a 和 b 所有可能的情况，时间复杂度为 O(c^2)。但是暴力枚举有一些情况是没有必要的。例如：当 c = 20 时，当 a = 1 的时候，枚举 b 的时候，只需要枚举到 b = 5 就可以结束了，这是因为 1^2 + 5^2 = 25 > 20。当 b > 5 时，一定有 1^2 + b^2 > 20。

注意到这一点，可以使用 sqrt 函数或者双指针降低时间复杂度。

方法一：使用 sqrt 函数

在枚举 a 的同时，使用 sqrt 函数找出 b。注意：本题 c 的取值范围在 [0,2^{31} - 1]，因此在计算的过程中可能会发生 int 型溢出的情况，需要使用 long 型避免溢出。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
var judgeSquareSum = function(c) {
    for (let a = 0; a * a <= c; a++) {
        const b = Math.sqrt(c - a * a);
        if (b === parseInt(b)) {
            return true;
        }
    }
    return false;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
func judgeSquareSum(c int) bool {
    for a := 0; a*a <= c; a++ {
        rt := math.Sqrt(float64(c - a*a))
        if rt == math.Floor(rt) {
            return true
        }
    }
    return false
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int)b) {
                return true;
            }
        }
        return false;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
bool judgeSquareSum(int c) {
    for (long a = 0; a * a <= c; a++) {
        double b = sqrt(c - a * a);
        if (b == (int)b) {
            return true;
        }
    }
    return false;
}

复杂度分析

  • 时间复杂度：O(\sqrt{c})。枚举 a 的时间复杂度为 O(\sqrt{c})，对于每个 a 的值，可在 O(1) 的时间内寻找 b。

  • 空间复杂度：O(1)。

方法二：双指针

不失一般性，可以假设 a \le b。初始时 a = 0，b = \sqrt{c，进行如下操作：

  • 如果 a^2 + b^2 = c，我们找到了题目要求的一个解，返回 true；
  • 如果 a^2 + b^2 < c，此时需要将 a 的值加 1，继续查找；
  • 如果 a^2 + b^2 > c，此时需要将 b 的值减 1，继续查找。

当 a = b 时，结束查找，此时如果仍然没有找到整数 a 和 b 满足 a^2 + b^2 = c，则说明不存在题目要求的解，返回 false。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var judgeSquareSum = function(c) {
    let left = 0;
    let right = Math.floor(Math.sqrt(c));
    while (left <= right) {
        const sum = left * left + right * right;
        if (sum === c) {
            return true;
        } else if (sum > c) {
            right--;
        } else {
            left++;
        }
    }
    return false;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func judgeSquareSum(c int) bool {
    left, right := 0, int(math.Sqrt(float64(c)))
    for left <= right {
        sum := left*left + right*right
        if sum == c {
            return true
        } else if sum > c {
            right--
        } else {
            left++
        }
    }
    return false
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool judgeSquareSum(int c) {
        long left = 0;
        long right = (int)sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
};
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool judgeSquareSum(int c) {
    long left = 0;
    long right = (int)sqrt(c);
    while (left <= right) {
        long sum = left * left + right * right;
        if (sum == c) {
            return true;
        } else if (sum > c) {
            right--;
        } else {
            left++;
        }
    }
    return false;
}

复杂度分析

  • 时间复杂度：O(\sqrt{c})。最坏情况下 a 和 b 一共枚举了 0 到 \sqrt{c 里的所有整数。

  • 空间复杂度：O(1)。

方法三：数学

费马平方和定理告诉我们：

一个非负整数 c 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k + 3 的质因子的幂均为偶数。

证明请见 这里 。

因此我们需要对 c 进行质因数分解，再判断所有形如 4k + 3 的质因子的幂是否均为偶数即可。

[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean judgeSquareSum(int c) {
        for (int base = 2; base * base <= c; base++) {
            // 如果不是因子，枚举下一个
            if (c % base != 0) {
                continue;
            }

            // 计算 base 的幂
            int exp = 0;
            while (c % base == 0) {
                c /= base;
                exp++;
            }

            // 根据 Sum of two squares theorem 验证
            if (base % 4 == 3 && exp % 2 != 0) {
                return false;
            }
        }

      	// 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
      	// 因此在退出循环以后需要再做一次判断
        return c % 4 != 3;
    }
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var judgeSquareSum = function(c) {
    for (let base = 2; base * base <= c; base++) {
        // 如果不是因子，枚举下一个
        if (c % base !== 0) {
            continue;
        }

        // 计算 base 的幂
        let exp = 0;
        while (c % base == 0) {
            c /= base;
            exp++;
        }

        // 根据 Sum of two squares theorem 验证
        if (base % 4 === 3 && exp % 2 !== 0) {
            return false;
        }
    }

    // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
    // 因此在退出循环以后需要再做一次判断
    return c % 4 !== 3;
};
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func judgeSquareSum(c int) bool {
    for base := 2; base*base <= c; base++ {
        // 如果不是因子，枚举下一个
        if c%base > 0 {
            continue
        }

        // 计算 base 的幂
        exp := 0
        for ; c%base == 0; c /= base {
            exp++
        }

        // 根据 Sum of two squares theorem 验证
        if base%4 == 3 && exp%2 != 0 {
            return false
        }
    }

    // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
    // 因此在退出循环以后需要再做一次判断
    return c%4 != 3
}
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int base = 2; base * base <= c; base++) {
            // 如果不是因子，枚举下一个
            if (c % base != 0) {
                continue;
            }

            // 计算 base 的幂
            int exp = 0;
            while (c % base == 0) {
                c /= base;
                exp++;
            }

            // 根据 Sum of two squares theorem 验证
            if (base % 4 == 3 && exp % 2 != 0) {
                return false;
            }
        }

        // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
        // 因此在退出循环以后需要再做一次判断
        return c % 4 != 3;
    }
};
[sol3-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool judgeSquareSum(int c) {
    for (int base = 2; base * base <= c; base++) {
        // 如果不是因子，枚举下一个
        if (c % base != 0) {
            continue;
        }

        // 计算 base 的幂
        int exp = 0;
        while (c % base == 0) {
            c /= base;
            exp++;
        }

        // 根据 Sum of two squares theorem 验证
        if (base % 4 == 3 && exp % 2 != 0) {
            return false;
        }
    }

    // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
    // 因此在退出循环以后需要再做一次判断
    return c % 4 != 3;
}

复杂度分析

  • 时间复杂度：O(\sqrt{c})。

  • 空间复杂度：O(1)。

📚 好读书？读好书！让时间更有价值| 世界读书日

4 月 22 日至 4 月 28 日，进入「学习 」，完成页面右上角的「让时间更有价值」限时阅读任务，可获得「2021 读书日纪念勋章」。更多活动详情戳上方标题了解更多👆

今日学习任务：

 Comments
On this page
0633-平方数之和
  1. 📚 好读书？读好书！让时间更有价值| 世界读书日