2026-03-15：数位平方和的最大值。用go语言，给定两个正整数 num 和 sum。我们要在所有满足以下两个条件的正整数中寻找最佳解： - 该数正

福大大架构师每日一题

发布于 2026-03-31 21:07:42

790

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-03-15：数位平方和的最大值。用go语言，给定两个正整数 num 和 sum。我们要在所有满足以下两个条件的正整数中寻找最佳解：

• 该数正好由 num 位构成；
• 各位数字相加的总和等于 sum。

对每一个满足上述条件的数，按照它各位数字的平方和来评估其得分。目标是找出得分最高的那一个，并以字符串形式返回该数；如果有多个得分相同的候选者，则返回数值较大的那个；如果不存在任何满足条件的数，则返回空字符串。

1 <= num <= 200000。

1 <= sum <= 2000000。

输入: num = 2, sum = 3。

输出: "30"。

解释:

有 3 个好整数：12、21 和 30。

12 的分数是。

21 的分数是。

30 的分数是。

最大分数是 9，由好整数 30 获得。因此，答案是 "30"。

题目来自力扣3723。

一、前置条件判断（第一步：合法性校验）

题目要求构造一个 num 位正整数，满足两个硬性条件：

1. 数字总位数 = num
2. 所有位上的数字之和 = sum

首先要判断是否存在满足条件的数：

• 单个数字最大是9，num 位数字的最大可能和 = num × 9
• 如果 sum > num×9：没有任何数字能满足和为sum，直接返回空字符串
• 如果 sum < 1：也不满足正整数要求，返回空字符串
• 其余情况：存在合法数字，进入下一步构造

对应示例：num=2，sum=3 2×9=18 ≥ 3，合法，继续计算。

二、核心数学原理（解题关键）

我们的目标：

1. 让各位数字的平方和最大（首要目标）
2. 若平方和相同，让数字本身最大（次要目标）

关键数学结论：

在数字总和固定的前提下： ✅ 数字越大、越集中，平方和越大 ❌ 数字越分散、越小，平方和越小

举例：总和=3

• 3+0 → 平方和=9+0=9（最大）
• 2+1 → 平方和=4+1=5
• 1+2 → 平方和=1+4=5

同时：要让数字本身最大，必须把大数字放在高位。

三、最优数字构造步骤（分4步）

基于上述结论，构造最优解的逻辑是：

步骤1：尽可能多地使用数字9

9是单个数字中平方最大的数，优先用9能最大化平方和。计算能放多少个连续的9： 9的个数 = sum ÷ 9（整除结果）

示例：sum=3，3÷9=0 → 0个9

步骤2：处理剩余的数值

sum除以9后会有余数： 余数 = sum % 9 这个余数就是除了9之外，唯一需要的非零数字。

示例：3%9=3 → 余数=3

步骤3：拼接核心数字段

把「所有9」+「余数」拼接在一起，这一段是平方和最大的数字组合。

示例：0个9 + 3 → 核心段="3"

步骤4：补全位数，保证数字最大

总位数要求是num位，前面的核心段长度不足，需要补0：

• 补0的数量 = num - 核心段长度
• 0必须补在最后面（保证高位数字最大）

示例：num=2，核心段长度=1 → 补1个0 最终结果：3 + 0 = "30"

四、完整逻辑验证（以示例为例）

1. 校验：2位数字最大和18≥3，合法
2. 最大化平方和：优先用大数字，总和3，最优组合是3和0
3. 保证数字最大：把大数字3放高位，0放低位 → 30
4. 输出结果：30

五、时间复杂度分析

整个算法只做了固定次数的数学计算和字符串拼接：

1. 合法性判断：O(1)
2. 计算9的个数、余数：O(1)
3. 字符串拼接：拼接长度为 num 的字符串，时间取决于 num 的长度
- • 生成9的字符串：O(sum/9)
- • 生成余数字符：O(1)
- • 生成补位0：O(num - len(核心段))

总时间复杂度：O(num) （num 是数字的位数，最大200000，线性时间）

六、额外空间复杂度分析

额外空间指除输入输出外，程序运行需要的临时空间：

1. 只存储了最终的结果字符串，长度为 num
2. 无递归、无数组、无哈希表等额外数据结构

总额外空间复杂度：O(num) （仅用于存储最终的数字字符串）

总结

1. 解题过程：合法性校验 → 用9最大化平方和 → 处理余数 → 高位放大数、低位补0
2. 核心思想：固定和下，数字越大越集中，平方和越大
3. 时间复杂度：O(num)（线性时间）
4. 额外空间复杂度：O(num)（仅存储结果字符串）

Go完整代码如下：

package main

import (
    "fmt"
    "strings"
)

func maxSumOfSquares(n, sum int)string {
    if n*9 < sum {
        return""
    }
    ans := strings.Repeat("9", sum/9)
    if sum%9 > 0 {
        ans += string('0' + byte(sum%9))
    }
    return ans + strings.Repeat("0", n-len(ans))
}

func main() {
    num := 2
    sum := 3
    result := maxSumOfSquares(num, sum)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_sum_of_squares(n, total_sum):
    """
    返回一个长度为n的数字字符串，使得各位数字之和为total_sum，
    并且数字的平方和最大（即尽可能把大的数字放在高位）
    """
    if n * 9 < total_sum:
        return""
    
    # 尽可能多地放置9
    ans = "9" * (total_sum // 9)
    
    # 如果还有剩余的和，放在中间
    remainder = total_sum % 9
    if remainder > 0:
        ans += str(remainder)
    
    # 补足剩余的0
    ans += "0" * (n - len(ans))
    
    return ans

def main():
    num = 2
    total_sum = 3
    result = max_sum_of_squares(num, total_sum)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <string>

std::string maxSumOfSquares(int n, int sum) {
    if (n * 9 < sum) {
        return"";
    }

    std::string ans;

    // 尽可能多地放置9
    ans.append(sum / 9, '9');

    // 如果还有剩余的和，放在中间
    if (sum % 9 > 0) {
        ans += static_cast<char>('0' + sum % 9);
    }

    // 补足剩余的0
    ans.append(n - ans.length(), '0');

    return ans;
}

int main() {
    int num = 2;
    int sum = 3;
    std::string result = maxSumOfSquares(num, sum);
    std::cout << result << std::endl;
    return0;
}