问题
给定一个非负整数 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种算法的时间复杂度均为: 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3885。