Lintcode 697-は平方数の和か否かを判断する

ははは、この问题はネット上で意外にも解答を探し当てていないで、そこで自分のcopyはVSの中で何度もデバッグしてやっとACになって、最も良いアルゴリズムであることを保证しないで、时间の复雑度はO(nlogn)、空间の复雑度O(1)(循环の中で1つの二分の検索をネストしました)で、もし誰かが必要とするならば、分かち合います~

class Solution {
public:
    /*
     * @param : the given number
     * @return: whether whether there're two integers
     */
  bool isSquare(int n) {
	if (n < 0) {
		return false;
	}
	if (n == 0) return true;
	int low = 1;
	int high = n;
	int mid = (low + high) >> 1;
	while (low <= high) {
		int temp = n / mid;
		if (mid == temp && n == mid * temp) {
			return true;
		}
		if (temp < mid) {
			high = mid - 1;
		}
		if (temp >= mid) {
			low = mid + 1;
		}
		mid = (low + high) >> 1;
	}
	return false; // fix me!  
}
bool checkSumOfSquareNumbers(int num) {
	// write your code here
	if (num<0) return false;
	if (isSquare(num)) return true;
	for (int i = 1; i<=sqrt(num); i++)
	{
		int target = (num - i * i);
		if (!isSquare(target)) continue;
		int j = sqrt(num)+1;
		int mid = 0;
		while (i <= j)
		{
			mid = (i + j) / 2;
			if (sqrt(target)>mid)
				i = mid + 1;
			else if (sqrt(target)

やっと二分で検索できました~