题目

题目来源：力扣（LeetCode）

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 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 叉树，树的每一个节点的值都是平方数的和
  2. 每一个节点的值都是从根节点到当前节点的累加。而平方数的个数其实就是遍历到第几层的时候累加和等于target。我们只需要一层一层的遍历，也就是常说的BFS，当遇到累加的和等于target的时候直接返回当前的层数即可。
  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var numSquares = function (n) {
  6.   let neighbor = [];
  7.   let queue = new Set([0]) //使用set消除重复，优化效率
  8.   // 将 小于 n 的完全平方数放进 neighbor 数组中
  9.   for (let i = 1; i * i <= n; i++) {
  10.     neighbor.push(i * i);//注意这里是从小到大
  11.   }
  12.   // 树的第几层
  13.   let count = 0;
  14.   while (queue.size) {
  15.     let nextSet = new Set();
  16.     count++;
  17.     // 遍历当前层的所有节点
  18.     for (let v of queue) {
  19.       // 访问当前节点的子节点，类比于二叉树的左右子节点
  20.       for (let c of neighbor) {
  21.         // 子节点的值
  22.         let add = v + c;
  23.         // add 始终是完全平方数的和，当 add 等于 n 的时候 count 的值，即 组成和为 n 的完全平方数的个数
  24.         if (add === n) {
  25.           return count;
  26.         }
  28.         // 如果 和 大于 n ，终止内层循环
  29.         if (add > n) {
  30.           //后面都是更大的了
  31.           break;
  32.         }
  33.         nextSet.add(add);
  34.       }
  35.     }
  36.     queue = nextSet;
  37.   }
  38.   return count;
  39. };

四平方和定理

一个数学定理可以帮助解决本题：「四平方和定理」。
四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。

同时四平方和定理包含了一个更强的结论：当且仅当 n ≠ 4^k × (8m + 7) 时，n 可以被表示为至多三个正整数的平方和。因此，当 n = 4^k × (8m + 7) 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。

当 n / 4^k × (8m + 7) 时，我们需要判断到底多少个完全平方数能够表示 n，我们知道答案只会是 1, 2, 3 中的一个。

由1个，2个和4个完全平方数得到的n我们很容易判断，所以剩下的就是由3个完全平方数得到的n。我们分为4步走的战略：

  • 先判断是否能由1个平方数组成
  • 在判断是否能由4个平方数组成
  • 接着判断是否能由2个平方数组成
  • 如果上面都不成立，只能由3个平方数组成了。
  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var numSquares = function (n) {
  7.   // 判断由一个平方数组成的
  8.   // 如果 n 是平方数，直接返回 1 即可，表示 n 是由 1 个平方数组成
  9.   if (isPerfectSquare(n)) {
  10.     return 1;
  11.   }
  13.   // 判断由 4 个平方数组成的
  14.   if (checkAnswer4(n)) {
  15.     return 4;
  16.   }
  18.   // 判断 由 2 个平方数组成的
  19.   for (let i = 1; i * i <= n; i++) {
  20.     let j = n - i * i;
  21.     if (isPerfectSquare(j)) {
  22.       return 2;
  23.     }
  24.   }
  26.   // 剩下的只能由3个平方数组成了
  27.   // 如果上面都不成立，根据拉格朗日四平方和定理
  28.   // 只能由3个平方数组成了
  29.   return 3;
  30. }
  32. // 判断是否为完全平方数
  33. const isPerfectSquare = (x) => {
  34.   const y = Math.floor(Math.sqrt(x));
  35.   return y * y == x;
  36. }
  38. // 判断是否能表示为 4^k*(8m+7)
  39. const checkAnswer4 = (x) => {
  40.   // 如果 x 是 4 的倍数，就一直除以 4 
  41.   while (x % 4 == 0) {
  42.     x /= 4;
  43.   }
  45.   return x % 8 == 7;
  46. }