题目描述
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 < = n < = 10 4 1 <= n <= 10^41<=n<=104
思路1: 动态规划
我们考虑f[i]为第i个数需要的最少完全平方数的个数，枚举每个比他小的完全平方数j 2 j ^ 2j2,则有f [ i ] = f [ i − j 2 ] + 1 f[i] = f[i - j ^ 2] + 1f[i]=f[i−j2]+1， 这里的1就是j 2 j ^ 2j2, 我们枚举每个j的时间复杂度是 o(n \sqrt{n}n), 枚举i的时间复杂度为o(n)，总的时间复杂度为o ( n n ) o(n\sqrt{n})o(nn)。
代码1
classSolution{public:intnumSquares(intn){vector<int>f(n+1,0);unordered_set<int>s;// 记录这个数是不是完全平方数for(inti=1;i<=100;++i){s.insert(i*i);}for(inti=1;i<=n;++i){f[i]=INT_MAX;// 需要j^2一个, 剩下的i - j ^ 2的最少个数已经出现for(intj=1;j<=i/j;++j){f[i]=min(f[i],1+f[i-j*j]);}}returnf[n];}};思路2: 数学，四平方和定理
有两个结论：
- 任意一个正整数都可以被表示为至多四个正整数的平方和。
- 当且仅当n ≠ 4 k × ( 8 m + 7 ) n \neq 4^k \times (8m + 7)n=4k×(8m+7)时，n nn可以被表示为至多三个正整数的平方和。因此，当n = 4 k × ( 8 m + 7 ) n = 4^k \times (8m + 7)n=4k×(8m+7)时，n nn只能被表示为四个正整数的平方和。此时我们可以直接返回 4。
我们枚举答案的个数：
- 当 可以开方,o(1),答案为1；
- 当 可以表示成两个数完全平方和相加，o ( n ) o(\sqrt{n})o(n)，答案为2；
- 当 可以表示成n = 4 k × ( 8 m + 7 ) n = 4^k \times (8m + 7)n=4k×(8m+7)，o(logn), 答案为4；
- 否则答案为3；
- 因此，总的时间复杂度为o ( n ) o(\sqrt{n})o(n)。
代码2
classSolution{public:// 是否是完全平方数 o(1)boolisPerfectSquare(intx){inty=sqrt(x);returny*y==x;}// 是否是两个数完全平方相加 o(n ^ (1/2))boolisTwoPerfectSquareadd(intx){for(inti=1;i<=x/i;++i){intj=x-i*i;if(isPerfectSquare(j)){returntrue;}}returnfalse;}// 是否是4个数相加 o(logn)boolcheckAnswer4(intx){while(x%4==0){x/=4;}returnx%8==7;}intnumSquares(intn){if(isPerfectSquare(n))return1;if(checkAnswer4(n))return4;if(isTwoPerfectSquareadd(n))return2;return3;}};
