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 a² + b² = c. Example 1:

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

Example 2:

Input: 3
Output: False

---

给定一个非负整数c，问是否存在两个整数a和b，使得a² + b² = c。 简单题，首尾指针法，首尾指针分别指向[0,c]，根据a² + b² 和 c的大小，首指针++或者尾指针–。 但是这样性能太差，过不了大数据，其实尾指针只需要到sqrt(c)即可，因为如果b大于sqrt(c)的话，a² + b² 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)]，性能大幅提升。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时3MS。]]>