這道題有幾個(gè)數(shù)學(xué)做法比較有意思。

題目描述

給定一個(gè)非負(fù)整數(shù)c，你要判斷是否存在兩個(gè)整數(shù)a和b，使得a^2+b^2=c。

解法

1. 利用等差數(shù)列公式

已知等差數(shù)列公式：

而且有

因此可以將c每次減少一個(gè)奇數(shù)（每次奇數(shù)增大2）；看剩下的是否為一個(gè)平方數(shù)。
第一次減1，共減1的平方；
第二次減3，共減2的平方；
第三次減5，共減3的平方；
...
以此類推，直到減后為負(fù)數(shù)。

class Solution {
public:
  bool judgeSquareSum(int c) {
    int num1 = sqrt(c);
    if (num1 * num1 == c) { // 判斷c本身就是一個(gè)平方數(shù)
      return true;
    }
    num1 = c;
    for (int i = 1; i <= num1; i += 2) {
      num1 -= i; // 每次減去一個(gè)奇數(shù)
      int num2 = sqrt(num1);
      if (num2 * num2 == num1) {
        return true;
      }
    }
    return false; 
  }
};

2. 利用費(fèi)馬平方和定理

費(fèi)馬平方和定理（證明）：

一個(gè)非負(fù)整數(shù) c 如果能夠表示為兩個(gè)整數(shù)的平方和，當(dāng)且僅當(dāng) c 的所有形如 4k + 3 的質(zhì)因子的冪均為偶數(shù)。

因此我們需要對(duì) c 進(jìn)行質(zhì)因數(shù)分解，再判斷所有形如 4k + 3 的質(zhì)因子的冪是否均為偶數(shù)即可。

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int base = 2; base * base <= c; base++) {
            // 如果不是因子，枚舉下一個(gè)
            if (c % base != 0) {
                continue;
            }

            // 計(jì)算 base 的冪
            int exp = 0;
            while (c % base == 0) {
                c /= base;
                exp++;
            }

            // 根據(jù) Sum of two squares theorem 驗(yàn)證
            if (base % 4 == 3 && exp % 2 != 0) {
                return false;
            }
        }

        // 例如 11 這樣的用例，由于上面的 for 循環(huán)里 base * base <= c ，base == 11 的時(shí)候不會(huì)進(jìn)入循環(huán)體
        // 因此在退出循環(huán)以后需要再做一次判斷
        return c % 4 != 3;
    }
};

3. 使用sqrt函數(shù)

枚舉，本題 c 的取值范圍在 [0,2^31?1]，因此在計(jì)算的過(guò)程中可能會(huì)發(fā)生 int 型溢出的情況，需要使用 long 型避免溢出。

class Solution {
public:
  bool judgeSquareSum(int c) {
    for (long a = 0; a * a <= c; a++) {
      double b = sqrt(c - a * a)'
      if (b == (int)b) {
        return ture;
      }
    }
    return false;
  }
};

4. 雙指針

class Solution {
public:
    bool judgeSquareSum(int c) {
        long left = 0;
        long right = (int)sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
};