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: 5Output: TrueExplanation: 1 * 1 + 2 * 2 = 5

 

Example 2:

Input: 3Output: False

 

---

题目标签：Math

　　大家今天情人节快乐哈！祝贺单身狗们节日快乐! （美国时间还在 2/14）

　　我给大家唱首歌：single dog, single dog, single all the way... 刷题吧！

 

　　题目给了我们一个 c，让我们找到 a * a + b * b = c。

　　这里可以利用 two pointers， left 和 right，left = 0， right =  Math.sqrt(c)。

　　当 left 小于等于 right的情况下：sum = left * left + right * right

　　　　如果 sum 大于 c 的话，说明 需要更小的，right--；

　　　　如果 sum 小于 c 的话，说明 需要更大的，left++；

　　　　如果 sum 等于 c，返回 true。

 

 

Java Solution:

Runtime beats 85.71% 

完成日期：02/14/2018

关键词：Math

关键点：利用 two pointers 从 0 到 Math.sqrt(c) 的范围

1 class Solution  2 { 3     public boolean judgeSquareSum(int c)  4     { 5         int left = 0; 6         int right = (int)Math.sqrt(c); 7          8         while(left <= right) 9         {10             int sum = left * left + right * right;11             12             if(sum == c)13                 return true;14             else if(sum < c)15                 left++;16             else17                 right--;18             19         }20         21         return false;22     }23 }

参考资料：n/a

LeetCode 题目列表 - 

题目来源：https://leetcode.com/