如何优化Python代码以处理15位数字的同位数数位和匹配查找

需求是找到一个比给定数字更小、位数相同且数位总和相等的数字。现有Python代码如下，但仅能处理最多7位数字，无法支持15位数字的场景：

N = int(input())

sume = 0
lik = [int(x) for x in str(N)]
for k in range(len(lik)):
    sume += lik[k]

def get_sum(N):
    global sumd
    sumd = 0
    lis = [int(x) for x in str(N)]
    for k in range(len(lis)):
        sumd += lis[k]
    return sumd
cnt = 0
for i in range(N-1, 10**(len(str(N))-1)-1, -1):
    get_sum(i)
    if sumd == sume:
        print(i)
        break
    else:
        cnt += 1
if cnt == N - 10**(len(str(N))-1):
    print(0)

原代码的问题 #

原代码采用暴力遍历方式，从N-1开始逐个检查直到最小的同位数数字。对于15位数字来说，遍历范围最多可达10^15次，时间复杂度完全不可接受；同时使用全局变量sumd的写法不规范，数位和的计算效率也较低。

优化方案 #

采用数位调整策略，类似"前趋数"的生成逻辑，从右往左找到可调整的数位，直接构造符合条件的最大数字，无需遍历所有可能：

核心思路 #

1. 将数字转为字符列表（便于逐位操作），计算目标数位总和target_sum。
2. 从右往左遍历，找到第一个位置i：
   • 当前数位digits[i] > 0（可以减小）
   • 减小该数位后，剩余数位能够凑出需要的和（剩余和需满足0 <= remaining <= 剩余位数*9）
3. 把digits[i]减1，计算后面数位需要凑的剩余和remaining。
4. 为保证结果是最大的符合条件的数，从右往左填充9，直到remaining耗尽，剩余数值放在最左侧的剩余位置。
5. 若遍历完所有数位都无法构造符合条件的数，返回0。

优化后的代码 #

def find_smaller_same_digit_sum(n):
    digits = list(str(n))
    n_len = len(digits)
    target_sum = sum(int(c) for c in digits)
    
    # 从右往左找第一个可调整的数位
    for i in range(n_len-2, -1, -1):
        current_digit = int(digits[i])
        if current_digit == 0:
            continue
        
        # 计算调整当前数位后的前缀和
        prefix_sum = sum(int(c) for c in digits[:i]) + (current_digit - 1)
        remaining = target_sum - prefix_sum
        remaining_digits_count = n_len - i - 1
        
        # 验证剩余和是否可通过剩余数位凑出
        if 0 <= remaining <= remaining_digits_count * 9:
            digits[i] = str(current_digit - 1)
            # 从右往左填充9，耗尽剩余和
            j = n_len - 1
            while remaining > 9 and j > i:
                digits[j] = '9'
                remaining -= 9
                j -= 1
            # 填充剩余数值
            if j > i:
                digits[j] = str(remaining)
            # 中间未填充的位置补0
            for k in range(i+1, j):
                digits[k] = '0'
            
            result = int(''.join(digits))
            # 确保结果是n位数（无前置零）
            return result if result >= 10 ** (n_len - 1) else 0
    # 无符合条件的数时返回0
    return 0

# 运行示例
N = int(input())
print(find_smaller_same_digit_sum(N))

代码说明 #

• 时间复杂度为O(n)（n为数字位数），即使是15位数字也能瞬间处理。
• 直接构造结果，避免了暴力遍历的巨大开销。
• 处理了含零场景：跳过数位为0的位置（无法减小），填充剩余数位时优先用9保证结果最大。

内容的提问来源于stack exchange，提问作者Codeer