难度: Medium
给你一个整数 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 <= 104
Submission
运行时间: 42 ms
内存: 0.0 MB
class Solution:
def numSquares(self, n: int) -> int:
d = {x ** 2 for x in range(1, 101) if x ** 2 <= n}
if n in d:
return 1
for i in d:
if n - i in d:
return 2
for i in d:
for j in d:
if n - i - j in d:
return 3
return 4
Explain
该题解采用数学推导的方法，利用了四平方和定理：任何一个正整数都可以表示成不超过四个整数的平方之和。首先生成不超过n的完全平方数集合d，然后分四种情况判断：1.如果n本身在d中，则只需要1个数；2.如果n可以表示为d中两个数之和，则需要2个数；3.如果n可以表示为d中三个数之和，则需要3个数；4.根据四平方和定理，剩下的情况只能由4个完全平方数组成。
时间复杂度: O(n^(3/2))
空间复杂度: O(sqrt(n))
class Solution:
def numSquares(self, n: int) -> int:
# 生成不超过n的完全平方数集合d
d = {x ** 2 for x in range(1, 101) if x ** 2 <= n}
# 情况1：n本身是完全平方数
if n in d:
return 1
# 情况2：n可以由d中两个数之和表示
for i in d:
if n - i in d:
return 2
# 情况3：n可以由d中三个数之和表示
for i in d:
for j in d:
if n - i - j in d:
return 3
# 情况4：n只能由d中四个数之和表示
return 4
Explore
在生成完全平方数集合时选择1至101的范围是因为101^2=10201，这是超过10000的第一个完全平方数。对于任何小于或等于10000的n，这个范围内的完全平方数集合是足够的。然而，如果n大于10000，我们需要增加范围，确保集合中包含所有不超过n的完全平方数。因此，动态确定范围上限为sqrt(n)是更合适的选择。
在判断n是否可以由d中两个数之和表示时，采用的是双循环遍历，这种方法的时间复杂度是O(m^2)，其中m是集合d的大小。对于大的n，这种方法的效率较低。更优化的方式可以使用双指针方法或哈希表来减少查找时间，尤其是哈希表方法，可以将时间复杂度降至O(m)。
这一结论基于著名的四平方和定理（Lagrange's Four Square Theorem），该定理表明每个正整数都可以表示为四个整数的平方和。因此，如果n不能通过一个、两个或三个完全平方数的和来表示，根据四平方和定理，它一定可以由四个数的平方和来表示。
动态规划方法在处理此类问题时通常更有效，因为它能够避免重复计算并保持子问题的最优解。动态规划的解法会使用一个数组dp，其中dp[i]表示组成数字i需要的最少的完全平方数数量。通过从低到高计算每个dp值，可以确保每步都是基于最优子结构进行的。相比之下，直接计算可能会涉及重复的计算和更高的时间复杂度。因此，对于大的n，动态规划通常更高效。