题目描述
给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数指的是一个整数，其值等于另一个整数的平方。 比如：
-
1 = 1 * 1 -
4 = 2 * 2 -
9 = 3 * 3 -
16 = 4 * 4
这些都属于完全平方数。
示例分析
示例 1
输入: n = 12
输出: 3
解释：
12 = 4 + 4 + 4
所以最少需要 3 个完全平方数。
示例 2
输入: n = 13
输出: 2
解释：
13 = 4 + 9
所以最少需要 2 个完全平方数。
解题思路
这道题很多同学第一次看到，会先想到动态规划。 但你给出的这份代码其实是用 BFS（广度优先搜索） 来做的，而且思路非常巧妙。
核心想法是：
把“一个数减去某个完全平方数”看成一次状态转移。
例如：
n = 12
我们可以从 12 出发：
-
减去
1，得到11 -
减去
4，得到8 -
减去
9，得到3
这就相当于从状态 12 可以走到多个新状态。
于是整道题就变成了：
从
n出发，每次减去一个完全平方数，最少走几步能到达0？
这其实就是一个最短路径问题，而 BFS 最擅长解决的正是“无权图中的最短路径”。
为什么 BFS 可以做这题
我们把每一个数字看成图中的一个节点。
如果当前数字是 cur，那么我们可以尝试减去所有不超过它的完全平方数：
cur - 1^2
cur - 2^2
cur - 3^2
...
每减去一次完全平方数，就相当于走了一步。
于是：
-
第 1 层表示：用了 1 个完全平方数后可以得到的所有结果
-
第 2 层表示：用了 2 个完全平方数后可以得到的所有结果
-
第 3 层表示：用了 3 个完全平方数后可以得到的所有结果
当某一层第一次出现 0 时，就说明：
当前层数就是最少需要的完全平方数个数
这就是为什么 BFS 中的 level 恰好可以表示答案。
你的代码
class Solution {
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
int level = 0;
queue.add(n);
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
int cur = queue.poll();
for (int j = 1; j * j <= cur; j++) {
int next = cur - j * j;
if (next == 0) {
return level;
}
if (!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
}
return -1;
}
}
这份代码的思路非常标准，整体流程就是：
-
从
n开始做 BFS -
每一层尝试减去所有可能的完全平方数
-
如果减到
0，说明当前层数就是最优答案 -
用
visited去重，避免重复搜索
BFS 中的 level 为什么是答案
这是这道题最关键的一点。
在 BFS 中：
-
第 1 层：表示从
n经过 1 次减法能到达的状态 -
第 2 层：表示经过 2 次减法能到达的状态
-
第 3 层：表示经过 3 次减法能到达的状态
而每次减法本质上就是“使用了一个完全平方数”。
所以：
第几层第一次到达
0，就表示最少用了几个完全平方数。
这就是 BFS 的天然优势： 第一次到达目标时，一定是步数最少的时候。
代码解析
1. 定义队列和去重集合
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
-
queue：用来做 BFS，保存当前待处理的数字状态 -
visited：记录已经访问过的状态，避免重复入队
2. 定义层数
int level = 0;
level 表示当前 BFS 走到了第几层。 也可以理解为：当前已经使用了多少个完全平方数。
3. 起点入队
queue.add(n);
我们从 n 这个状态开始出发。
4. BFS 主循环
while (!queue.isEmpty()) {
只要队列不为空，就继续做广度优先搜索。
5. 记录当前层节点数，并进入下一层
int size = queue.size();
level++;
这里 size 表示当前层有多少个状态。 每处理完这一层，说明又多用了一个完全平方数，所以 level++。
6. 依次处理当前层的每个状态
for (int i = 0; i < size; i++) {
int cur = queue.poll();
从队列中取出当前数字 cur。
7. 枚举所有可能减去的完全平方数
for (int j = 1; j * j <= cur; j++) {
int next = cur - j * j;
这里枚举：
-
1^2 -
2^2 -
3^2 -
…
直到 j * j <= cur 为止。
每次减去一个完全平方数，得到下一个状态 next。
8. 如果减到 0，直接返回当前层数
if (next == 0) {
return level;
}
这说明：
-
当前用了
level个完全平方数 -
并且第一次成功凑到了
n
由于 BFS 是按层扩展的，所以这一定是最少个数。
9. 没访问过的状态才入队
if (!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
如果这个状态之前没有处理过，就加入队列。
为什么一定要去重？
因为同一个数字可能会通过不同路径重复到达。 如果不去重，搜索树会急剧膨胀，效率会差很多。
10. 理论上的兜底返回
return -1;
正常情况下不会走到这里，因为根据题意总能拆成若干个平方数。 这里只是一个形式上的兜底。
示例推演
我们以：
n = 12
为例。
第 1 层
初始：
queue = [12]
level = 1
处理 12：
-
12 - 1 = 11 -
12 - 4 = 8 -
12 - 9 = 3
所以第 1 层结束后：
queue = [11, 8, 3]
说明用了 1 个完全平方数后，可以得到这些状态。
第 2 层
现在：
level = 2
处理 11：
-
11 - 1 = 10 -
11 - 4 = 7 -
11 - 9 = 2
处理 8：
-
8 - 1 = 7 -
8 - 4 = 4
处理 3：
-
3 - 1 = 2
去重后，队列中会有若干新状态。
第 3 层
继续往下扩展时，会遇到：
4 - 4 = 0
于是返回：
3
说明：
12 = 4 + 4 + 4
最少需要 3 个完全平方数。
再看 n = 13
初始：
queue = [13]
第 1 层
-
13 - 1 = 12 -
13 - 4 = 9 -
13 - 9 = 4
得到：
[12, 9, 4]
第 2 层
处理 9 时：
9 - 9 = 0
于是返回：
2
说明：
13 = 4 + 9
最少需要 2 个完全平方数。
为什么 visited 很重要
比如某个数字 7，可能既能由：
11 - 4
得到，也能由：
8 - 1
得到。
如果不加 visited，那么 7 会被重复入队、重复搜索，造成大量重复计算。
所以：
HashSet<Integer> visited = new HashSet<>();
是 BFS 能高效运行的关键之一。
这题和动态规划的关系
这道题其实也可以用动态规划来做。
比如定义：
dp[i] = 和为 i 的完全平方数的最少数量
转移方程是：
dp[i] = min(dp[i - j*j] + 1)
动态规划和 BFS 都能解决这题。
BFS 的优点
-
思路很像“最短路”，比较直观
-
一旦搜到
0就能提前结束
动态规划的优点
-
写法更稳定
-
更像标准的完全背包 / 最值 DP 模型
你这份 BFS 写法非常适合拿来理解“最少步数 = BFS 分层”的思想。
复杂度分析
假设每个状态最多会尝试 sqrt(n) 个平方数。
时间复杂度
一般可以写成：
O(n * sqrt(n))
因为每个小于等于 n 的状态最多访问一次，而每次会枚举若干个平方数。
空间复杂度
O(n)
因为队列和 visited 最坏情况下都可能存储不少状态。
总结
不是在凑平方数，而是在图上找从 n 到 0 的最短路径。
每次减去一个完全平方数，就相当于走一步。 因此：
-
把
n当作起点 -
每次减去一个平方数扩展到下一层
-
第一次到达
0时，层数就是答案
你可以把这题总结成一句话：
完全平方数最少个数，本质就是从 n 走到 0 的最短步数，BFS 分层刚好解决。
这是一道非常经典的“数论外壳 + 图论思维”的题，值得彻底掌握。
