如何计算正整数数组所有a[i]∘a[j]拼接组合的总和？

问题描述 #

给定一个正整数数组a，计算所有可能的a[i]∘a[j]的总和，其中a[i]∘a[j]指将a[i]和a[j]转换为字符串后拼接，再转回整数的结果。

示例 #

• 示例1：当a = [10, 2]时，总和为1010 + 102 + 210 + 22 = 1344
• 示例2：当a = [8]时，总和为88
• 示例3：当a = [1, 2, 3]时，总和为11+12+13+21+22+23+31+32+33 = 198

解法分析 #

直接遍历所有i,j组合拼接字符串转整数计算，在数组规模较大时会有性能瓶颈。我们可以通过数学规律优化计算：
对于任意a[i]和a[j]，a[i]∘a[j]等价于：
a[i] * 10^len(str(a[j])) + a[j]

因此，总和可以拆解为两部分：

1. 所有a[i] * 10^len(str(a[j]))的和 = sum(a) * sum(10 ** len(str(num)) for num in a)
2. 所有a[j]的和，每个a[j]会被计算n次（n为数组长度）= sum(a) * n

最终总和为两部分相加，这样可以将时间复杂度从O(n²)降到O(n)。

代码实现 #

优化解法（Python） #

def solution(a):
    sum_a = sum(a)
    n = len(a)
    sum_10_pows = sum(10 ** len(str(num)) for num in a)
    return sum_a * sum_10_pows + sum_a * n

暴力解法（适合小数组验证） #

def solution_bruteforce(a):
    total = 0
    for i in range(len(a)):
        for j in range(len(a)):
            total += int(str(a[i]) + str(a[j]))
    return total

验证示例 #

• 输入[10,2]：优化解法计算(10+2)*(100+10) + (10+2)*2 = 12*110 +12*2=1320+24=1344，与示例结果一致。
• 输入[8]：8*(10) +8*1=80+8=88，正确。
• 输入[1,2,3]：(1+2+3)*(10+10+10) +6*3=6*30+18=180+18=198，正确。

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