C#LeetCode刷题之#633-平方数之和( Sum of Square Numbers)

问题

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

输入: 5

输出: True

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

输入: 3

输出: False

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5

Input: 3

Output: False

示例

public class Program {

    public static void Main(string[] args) {
        var num = 3;
        var res = CheckSumOfSquareNumbers(num);
        Console.WriteLine(res);

        num = 5;
        res = CheckSumOfSquareNumbers2(num);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool CheckSumOfSquareNumbers(int c) {
        //算是暴力解法
        //不过没必要全部计算,否则肯定TLE
        var sqrt = (int)Math.Sqrt(c);
        for(var i = 0; i <= sqrt; i++) {
            //计算值 c - i * i
            double k = Math.Sqrt(c - i * i);
            //判定是否相待,这是常用的判定开根号与目标值是否相等的写法
            if((int)k == k) return true;
        }
        return false;
    }

    private static bool CheckSumOfSquareNumbers2(int c) {
        //双指针法
        var sqrt = (int)Math.Sqrt(c);
        //存放计算 平方的和 的值
        var sum = 0;
        //前后指针
        var i = 0;
        var j = sqrt;
        //指针碰撞时为止
        while(i <= sqrt) {
            sum = i * i + j * j;
            if(sum < c) {
                i++;
            } else if(sum > c) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

False
True

分析:

显而易见,以上2种算法的时间复杂度均为: O(n)

C#LeetCode刷题之#633-平方数之和( Sum of Square Numbers)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3885

发表评论

登录后才能评论