279.Perfect Squares

Tags: Medium Breadth-first Search Math Dynamic Programming

Links: https://leetcode.com/problems/perfect-squares/

---

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

---

每个数字可以使用无限多次，其实可以看成完全背包，但是有个很重要的点是，完全背包需要开一个和n等大的数组，如果n为$10^9$，显然会超过内存限制。只不过这个题比较友好，测试数据没有这种数据。

那么还是用数学的解法来解决，需要了解拉格朗日四平方和定理、勒让德三平方和定理和费马平方和定理。

四平方和定理又称拉格朗日定理（Lagrange's Four-square Theorem），定理指出每个正整数均可表示为4个整数的平方和。

勒让德三平方和定理（Legendre's three-square theorem）指出，如果自然数n可以写成$n = 4^a(8b+7)$的形式，其中a, b都是整数，那么自然数**无法**写成三个平方数之和的形式$n = x^2 + y^2 + z^2$。

费马平方和定理（Fermat square sum theorem）指出，**奇质数**可以表示成两个平方数之和的充要条件是该质数被4除余1。

那么这个题的思路就是：

• 首先判断数字是否是完全平方数，时间复杂度$O(1)$
• 然后看是否满足勒让德三平方和定理，不满足则必然只能写成4个数的平方和，时间复杂度$O(\log n)$
• 暴力枚举判断是否可以写成两个数的平方和，时间复杂度$O(\sqrt n)$
• 如果都不满足，则只能是三个数的平方和

所以时间复杂度是$O(\sqrt n + \log n)$， 空间复杂度是$O(1)$。

class Solution {
public:
    int numSquares(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        //首先判断是否是完全平方数
        int k = sqrt(n);
        if (k * k == n) return 1;

        //判断是否满足勒让德三平方和定理
        int tmp = n;
        while ((tmp & 3) == 0) tmp >>= 2;
        if (((tmp - 7) & 7) == 0) return 4;

        //枚举是否可以表示成连个数的平方和
        for (int i = 1; i * i <= n; ++i) {
            int q = sqrt(n - i * i);
            if (i * i + q * q == n) return 2;
        }

        return 3;
    }
};