如何优化数组整数两两拼接转数值后的求和效率？

原代码通过双重循环拼接字符串再转整数的方式，时间复杂度为O(n²)，当数组规模较大时（比如n≥1e4），会因循环次数过多+字符串转换开销导致超时，缓存字符串只能优化转换环节，无法解决双重循环的本质性能瓶颈。

核心优化思路：用数学公式替代字符串拼接 #

对于任意两个元素ai和aj，拼接结果ai º aj可以转化为数学表达式：

ai * 10^m + aj，其中m是aj的十进制位数（例如aj=2时m=1，aj=123时m=3）

基于这个公式，所有拼接结果的总和可以拆分为两部分计算：

1. 所有ai * 10^m_j的和：可以拆解为数组元素总和 × 所有元素对应10的位数次方的总和，因为每个ai需要乘以所有aj对应的10^m_j，无需双重循环。
2. 所有aj的和：每个aj会被遍历len(a)次（对应每个ai），因此总和为数组元素总和 × 数组长度。

最终总和公式为：
sum_a * sum_10_pows + sum_a * len(a)
其中：

• sum_a：数组所有元素的和
• sum_10_pows：每个元素aj对应的10^m_j的总和（m_j是aj的位数）

代码实现 #

def concatenationSum(a):
    sum_a = sum(a)
    sum_10_pows = 0
    arr_length = len(a)
    for num in a:
        # 计算当前数字的位数对应的10的幂次
        # 方法1：用字符串快速获取位数
        digit_count = len(str(num))
        # 方法2：数学方法获取位数（避免字符串转换，极端场景下更快）
        # digit_count = 0
        # temp = num
        # while temp > 0:
        #     digit_count += 1
        #     temp = temp // 10
        sum_10_pows += 10 ** digit_count
    return sum_a * sum_10_pows + sum_a * arr_length

性能提升说明 #

优化后时间复杂度从O(n²)降至O(n)，每个元素仅需处理一次，无论是字符串转位数还是数学方法求位数，都是常数级开销，完全能应对大规模数组的测试用例。

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