C#刷遍Leetcode面试题系列连载（4） No.633 - 平方数之和

2023-01-09 16:06:06

上篇文章中一道数学问题 - 自除数，今天我们接着分析 LeetCode 中的另一道数学题吧~

系列教程索引

传送门：https://enjoy233.cnblogs.com/articles/leetcode_csharp_index.html

今天要给大家分析的面试题是 LeetCode 上第 633 号问题，

Leetcode 633 - 平方数之和

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

题目描述

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

示例1:

输入: 5

输出: True

解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3

输出: False

Input:

Expected answer:

true

true

true

题目难度: 简单
贡献者： Stomach_ache

相关话题

数学

https://leetcode-cn.com/tag/math

相似题目

有效的完全平方数

https://leetcode-cn.com/problems/valid-perfect-square

解题思路:

做一次循环，用目标和减去循环变量的平方，如果剩下的部分依然是完全平方的情形存在，就返回true；否则返回false。

假定 $i \leq a \leq b $，根据数据的对称性，循环变量 i 只需取到 $i^2 \cdot 2 \leq c $ 即可覆盖所有情形.

已AC代码:

最初版本:

public class Solution

{

    public bool JudgeSquareSum(int c)

    {

        for (int i = 0; c - 2 * i * i >= 0; i++)

        {

            double diff = c - i*i;

            if ((int)(Math.Ceiling(Math.Sqrt(diff))) == (int)(Math.Floor(Math.Sqrt(diff))))  // 若向上取整=向下取整，则该数开方后是整数

                return true;

        }

        return false;

    }

}

Rank:

执行用时: 56 ms, 在所有 csharp 提交中击败了68.18%的用户.

优化1:

public class Solution

{

    public bool JudgeSquareSum(int c)

    {

        for (int i = 0; c - 2 * i * i >= 0; i++)

        {

            int diff = c - i*i;

            if (IsPerfectSquare(diff))

                return true;

        }

        return false;

    }

    private bool IsPerfectSquare(int num)

    {

        double sq1 = Math.Sqrt(num);

        int sq2 = (int)Math.Sqrt(num);

        if (Math.Abs(sq1 - (double)sq2) < 10e-10)

            return true;

        return false;

    }

}

Rank:

执行用时: 52 ms, 在所有 csharp 提交中击败了90.91%的用户.

优化2(根据文末参考资料[1]中MPUCoder 的回答改写):

public class Solution

{

    public bool JudgeSquareSum(int c)

    {

        for (int i = 0; i <= c && c - i * i >= 0; i++)

        {

            int diff = c - i*i;

            if (IsPerfectSquare(diff))

                return true;

        }

        return false;

    }

    public bool IsPerfectSquare(int num)

    {

        if ((0x0213 & (1 << (num & 15))) != 0)  //TRUE only if n mod 16 is 0, 1, 4, or 9

        {

            int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5);

            return t * t == num;

        }

        return false;

    }

}

Rank:

执行用时: 44 ms, 在所有 csharp 提交中击败了100.00%的用户.

优化3(根据文末参考资料[1]中 Simon 的回答改写):

public class Solution

{

    public bool JudgeSquareSum(int c)

    {

        for (int i = 0; c - i * i >= 0; i++)

        {

            long diff = c - i*i;

            if (IsSquareFast(diff))

                return true;

        }

        return false;

    }

    bool IsSquareFast(long n)

    {

        if ((0x2030213 & (1 << (int)(n & 31))) > 0)

        {

            long t = (long)Math.Round(Math.Sqrt((double)n));

            bool result = t * t == n;

            return result;

        }

        return false;

    }

}

Rank:

执行用时: 48 ms, 在所有 csharp 提交中击败了100.00%的用户.

另外，*上还推荐了一种写法：

public class Solution

{

    public bool JudgeSquareSum(int c)

    {

        for (int i = 0; c - 2 * i * i >= 0; i++)

        {

            double diff = c - i*i;

            if (Math.Abs(Math.Sqrt(diff) % 1) < 0.000001)

                return true;

        }

        return false;

    }

}

事实上，速度并不快~

Rank:

执行用时: 68 ms, 在所有 csharp 提交中击败了27.27%的用户.

双"指针" 解法:

左指针 l=0，右指针 r = √C，夹逼条件是 $ l^2 + r^2 = C $

时间复杂度 log(n), 感谢 @msp的昌伟哥哥的补充和指正~

    public class Solution

    {

        public bool JudgeSquareSum(int c)

        {

            var r = (int)Math.Sqrt(c);

            var l = 0;

            while (l <= r)

            {

                var sum = l * l + r * r;

                if (sum == c)

                    return true;

                if (sum < c)

                    l++;

                else

                    r--;

            }

            return false;

        }

        // 以下为测试

        public static void Main(string[] args)

        {

            var sol = new Solution();

            var res = sol.JudgeSquareSum(25);

            Console.WriteLine(res);

        }

    }