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种算法的时间复杂度均为： 。