LeetCode Sum of Square Numbers

LeetCode Sum of Square Numbers

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

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

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

简单题,首尾指针法,首尾指针分别指向[0,c],根据a2 + b2 和 c的大小,首指针++或者尾指针--。

但是这样性能太差,过不了大数据,其实尾指针只需要到sqrt(c)即可,因为如果b大于sqrt(c)的话,a2 + b2 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)],性能大幅提升。

代码如下:

class Solution {
public:
	bool judgeSquareSum(int c) {
		long long i = 0, j = sqrt(c) + 1;
		while (i <= j) {
			long long cur = i*i + j*j;
			if (cur == c)return true;
			else if (cur < c)++i;
			else --j;
		}
		return false;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *