更新时间：2025-04-02
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
279. 完全平方数
给你一个整数 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
方法一：动态规划
通过构建 dp 数组，其中 dp[i] 表示组成整数 i 所需的最少完全平方数的数量。利用动态规划逐步填充 dp 数组，最终得到 dp[n] 的值。
- 初始化：
dp[0] = 0（基础情况），其他位置初始化为最大值（如Integer.MAX_VALUE）。 - 状态转移：对于每个数
i，遍历所有可能的平方数j*j，更新dp[i] = min(dp[i], dp[i - j*j] + 1)。 - 遍历顺序：外层遍历目标值
i，内层遍历可能的平方数j。
代码实现(Java)：
class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0; // 初始条件// 遍历每个整数i，计算其最少平方数个数for (int i = 1; i <= n; i++) {// 遍历所有可能的平方数j*j（j*j <= i）for (int j = 1; j * j <= i; j++) {// 更新dp[i]为最小值dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}
方法二：四平方和定理(数学解法)
四平方和定理 (Lagrange’s four-square theorem) 说明每个正整数均可表示为4个整数的平方和。其中，当且仅当该数满足4^k*(8m+7)时只能表示为四平方和，其他形式都可以表示为三平方和。
- 检查是否为完全平方数：如果是，直接返回1。
- 检查是否满足形式4^k*(8m +7)：若是，返回4。
- 检查是否能表示为两个平方数之和：若是，返回2。
- 其他情况返回3：根据定理，剩余情况只需3个平方数。
代码实现(Java)：
class Solution {public int numSquares(int n) {// 判断是否为完全平方数if (isPerfectSquare(n)) {return 1;}// 检查是否满足4^k*(8m +7)的条件int num = n;while (num % 4 == 0) {num /= 4;}if (num % 8 == 7) {return 4;}// 检查是否可以表示为两个平方数的和for (int i = 1; i * i <= n; i++) {int j = n - i * i;if (isPerfectSquare(j)) {return 2;}}// 其他情况返回3return 3;}// 辅助函数，判断x是否为完全平方数private boolean isPerfectSquare(int x) {int s = (int) Math.sqrt(x);return s * s == x;}
}
复杂度分析
- 方法一时间复杂度：外层循环：
O(n)，内层循环：O(√i)，总复杂度：O(n√n)。 - 方法二时间复杂度：
O(√n)。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。