LeetCode 解題筆記：3723. Maximize Sum of Squares of Digits

作者：王一哲
日期：2026年10月14日


LeetCode 題目連結：3723. Maximize Sum of Squares of Digits

解題想法

中等難度題。題目給兩個整數 $num, sum$，代表共有 $num$ 個數字，所有數字加總等於 $sum$。對於符合這兩個條件的數字，其分數為每個位數平方的加總，找出分數最高的數字並以字串格式回傳，如果無解則回傳空字串。這題下方的提示基本上已經講清楚解法，原則上盡量選用數字 9，最後再加上剩下的數字或 0，如果最後找到的答案位數大於 $num$ 無解。

Python 程式碼

用 for 迴圈依序填入數字，速度很慢。Runtime: 2761 ms, beats 5.51%. Memory: 21.24 MB, beats 59.06%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        ans = ""  # 答案，字串格式
        rem = sum  # 位數加總
        # 每個位數都由 9 開始往下找，共執行 num 次
        for _ in range(num):
            for d in range(9, -1, -1):
                if rem >= d:
                    ans += str(d)
                    rem -= d
                    break
        return ans if rem == 0 else ""

計算需要填入的數字 9 數量以及餘數，速度快很多。Runtime: 4 ms, beats 74.02%. Memory: 20.87 MB, beats 90.55%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # 答案，字串格式，左側盡量用 9，如果 sum % 9 > 0，右側補上餘數
        ans = "9" * (sum // 9) + (str(sum % 9) if sum % 9 > 0 else "")
        # 長度不夠，補 0
        if len(ans) < num: ans += "0" * (num - len(ans))
        # 長度超過 num，無解
        return ans if len(ans) == num else ""

C++ 程式碼

用 for 迴圈依序填入數字，速度很慢。Runtime: 115 ms, beats 14.72%. Memory: 86.06 MB, beats 5.08%.

class Solution {
public:
    string maxSumOfSquares(int num, int sum) {
        string ans;  // 答案，字串格式
        int rem = sum;  // 位數加總
        // 每個位數都由 9 開始往下找，共執行 num 次
        for(int i = 0; i < num; i++) {
            for(int d = 9; d >= 0; d--) {
                if (rem >= d) {
                    ans += char(d + '0');
                    rem -= d;
                    break;
                }
            }
        }
        return (rem == 0 ? ans : "");
    }
};

計算需要填入的數字 9 數量以及餘數，速度快很多。Runtime: 55 ms, beats 71.57%. Memory: 85.09 MB, beats 5.08%.

class Solution {
public:
    string maxSumOfSquares(int num, int sum) {
        // 答案，字串格式，左側盡量用 9，如果 sum % 9 > 0，右側補上餘數
        string ans (sum / 9, '9');
        if (sum % 9 > 0) {
            ans += char(sum % 9 + '0');
        }
        // 長度不夠，補 0
        while((int)ans.size() < num) {
            ans += "0";
        }
        // 長度超過 num，無解
        return ((int)ans.size() == num ? ans : "");
    }
};