P171 两个完全平方数的和

描述#

这个题目说的是，给你一个非负整数 c，你要判断它是否可以分解成两个完全平方数的和。

比如说，给你的数字 c 等于 8：
c = 8
8 可以分解成 2 的平方加上 2 的平方，因此要返回 true。
c = 8 = 2^2 + 2^2
再比如说给你的数字 c 等于 7：
c = 7
7 不能分解成两个完全平方数的和，于是返回 false。

相关视频：求和为给定值的两个数，有序数组中求和为给定值的两个数

代码#

public class AlgoCasts {

  private boolean isSquare(int num) {
    int x = (int) Math.sqrt(num);
    return x * x == num;
  }

  // Time: O(c ^ 1/2), Space: O(1)
  public boolean judgeSquareSum(int c) {
    int x = (int) Math.sqrt(c);
    for (int i = 0; i <= x; ++i)
      if (isSquare(c - i*i))
        return true;
    return false;
  }

  // Time: O(c ^ 1/2), Space: O(c ^ 1/2)
  public boolean judgeSquareSumHashSet(int c) {
    int x = (int) Math.sqrt(c);
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i <= x; ++i) {
      set.add(i * i);
      if (set.contains(c - i*i))
        return true;
    }
    return false;
  }

  // Time: O(c ^ 1/2), Space: O(1)
  public boolean judgeSquareSumTwoPointer(int c) {
    int i = 0, j = (int) Math.sqrt(c);
    while (i <= j) {
      int sum = i*i + j*j;
      if (sum == c) return true;
      else if (sum > c) --j;
      else ++i;
    }
    return false;
  }

  // Time: O(c ^ 1/2), Space: O(1)
  public boolean judgeSquareSumMath(int c) {
    for (int i = 2; i*i <= c; ++i) {
      int cnt = 0;
      while (c % i == 0) {
        ++cnt;
        c /= i;
      }
      if (i % 4 == 3 && (cnt & 1) == 1) return false;
    }
    return c % 4 != 3;
  }

}