题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

https://leetcode-cn.com/problems/perfect-squares/

分析

四平方和定理：任何一个整数都可以表示为不超过4个数的平方和。

推论：当且仅当n=4^a(8b+7)时，n恰好可以表示为4个数的平方和

所以答案在1、2、3、4中的一个。

代码

        protected boolean isSquare(int n) {
            int sq = (int) Math.sqrt(n);
            return n == sq * sq;
        }

        public int numSquares(int n) {
            while (n % 4 == 0) {
                n /= 4;
            }
            if (n % 8 == 7) {
                return 4;
            }

            if (this.isSquare(n)) {
                return 1;
            }
            for (int i = 1; i * i <= n; ++i) {
                if (this.isSquare(n - i * i)) {
                    return 2;
                }
            }
            return 3;
        }