两数平方和

633 Sum of Square Numbers (Easy)

Leetcode / 力扣

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

题目描述：判断一个非负整数是否为两个整数的平方和。

可以看作是在 0~target 有序数组中查找两个数，让这两个数的平方和为 target，如果能找到，就返回 true，表示 target 是两个整数的平方和。

设右指针为 x，左指针固定为 0，为了使 0² + x² 的值尽可能接近 target，我们可以将 x 取为 sqrt(x)。

 public boolean judgeSquareSum(int target) {
     if (target < 0) return false;
     int i = 0, j = (int) Math.sqrt(target);
     while (i <= j) {
         int powSum = i * i + j * j;
         if (powSum == target) {
             return true;
         } else if (powSum > target) {
             j--;
         } else {
             i++;
         }
     }
     return false;
 }