当前位置：首页 > news >正文

从能算到秒杀：完全平方数与最少数量的数学真相

news 2026/5/22 3:28:13

LeetCode Hot 100 刷题笔记 · 第 15 篇

如果说「跳跃游戏 II」是在教你什么时候不得不跳，

那279. 完全平方数 就是在考你：

最少能用几个平方数，凑出一个整数？

这也是我第一次意识到：

有些动态规划，其实是在替你跑 BFS。

🟢 题目速览

LeetCode 279. 完全平方数（中等）

给你一个整数n，返回和为 n 的完全平方数的最少个数。

完全平方数示例：

1 = 1 × 1 4 = 2 × 2 9 = 3 × 3 16 = 4 × 4

示例

输入：n = 12 输出：3 解释：12 = 4 + 4 + 4

输入：n = 13 输出：2 解释：13 = 4 + 9

🧠 我的第一反应（很危险）

看到“最少数量”，直觉立刻冒出来：

BFS？
DP？
背包问题？

于是脑子里立刻出现：

dp[i] = min(dp[i - k*k] + 1)

❌ 问题也很明显：

时间复杂度 O(n√n)
面试如果再卡常数，容易翻车
没用到数学性质

Hot100 不可能这么简单 😂

🚀 真正解法一：BFS（最直观）

把这题看成一张图：

节点：数值 0 ~ n
边：减去一个完全平方数

求0 → n 的最短路径

class Solution { public int numSquares(int n) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n + 1]; queue.offer(0); visited[0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int cur = queue.poll(); for (int k = 1; k * k <= n; k++) { int next = cur + k * k; if (next == n) return steps + 1; if (next > n) break; if (!visited[next]) { visited[next] = true; queue.offer(next); } } } steps++; } return -1; } }

✅ 优点：思路清晰

❌ 缺点：队列 + 访问数组，略重

🚀 真正解法二：DP（工程最常用）

状态定义

dp[i] = 和为 i 的最少完全平方数个数

状态转移

dp[i] = min(dp[i - k*k] + 1)

代码（面试首选）

class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int k = 1; k * k <= i; k++) { dp[i] = Math.min(dp[i], dp[i - k * k] + 1); } } return dp[n]; } }

复杂度

时间复杂度：O(n√n)
空间复杂度：O(n)

✅ 稳定

✅ 易写

✅ 面试安全

🚀 真正解法三：数学定理（终极秒杀）

这是本题的灵魂。

🔑 拉格朗日四平方定理

任意正整数最多可以表示为 4 个完全平方数之和

进一步判断：

情况	结论
n 本身是完全平方数	1
n = a² + b²	2
n = 4^k × (8m + 7)	4
其他	3

代码（面试加分项）

class Solution { public int numSquares(int n) { // 1 个平方数 if (isSquare(n)) return 1; // 2 个平方数 for (int i = 1; i * i <= n; i++) { if (isSquare(n - i * i)) return 2; } // 4 个平方数 int m = n; while ((m & 3) == 0) m >>= 2; if ((m & 7) == 7) return 4; // 剩下一定是 3 return 3; } private boolean isSquare(int x) { int r = (int) Math.sqrt(x); return r * r == x; } }

✅ 时间复杂度：O(√n)

✅ 空间复杂度：O(1)

✅ 面试官直接点头