LeetCode求数组三角和Python解法提交超时排查咨询

Find Triangular Sum of an Array
题目要求：对数组反复执行相邻元素求和后模10的操作，直到数组仅剩1个元素，返回该元素值。

1. 致命逻辑缺陷（直接导致超时和结果错误） #

• 边界条件完全失效：当输入数组长度为1（题目允许的合法输入，比如用例[0]预期返回0），循环判断条件len(nums) != 2永远成立，每次循环生成空数组赋值给nums，程序直接陷入无限死循环，这是提交后大面积超时、仅通过1个用例的根本原因。
• 最后一步返回结果遗漏模10操作：当数组长度降到2时，两数之和可能大于等于10，比如[6,7]求和为13，直接返回13不符合题目每步取模10的要求，会出现结果错误。
• 循环迭代逻辑存在隐患：循环内用arrLen控制遍历范围，虽然第一次循环后arrLen会更新为新数组长度，但因为边界判断错误，遇到长度小于2的数组就会直接崩溃。

2. 效率可优化点 #

就算修复逻辑问题，原代码每轮迭代都新建列表、反复拷贝元素的写法也会带来额外内存和时间开销。虽然题目n最大为1000的规模下，O(n²)的模拟法完全可以通过，但可以通过原地修改数组进一步提速。如果追求极致效率，还可以利用杨辉三角的组合数数学性质，把时间复杂度降到O(n)。

from typing import List
class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        n = len(nums)
        for level in range(n, 1, -1):
            for i in range(level - 1):
                nums[i] = (nums[i] + nums[i+1]) % 10
        return nums[0]

这个版本直接在原数组上原地更新每一层的结果，不需要额外新建数组，没有多余拷贝操作，边界处理覆盖了长度为1的输入场景，所有步骤都做了模10处理，可以通过全部测试用例。

三角求和的最终结果本质是原数组每个元素乘以杨辉三角第n-1行对应位置的组合数系数，求和后再模10，公式为：
$$res = \left( \sum_{i=0}^{n-1} C_{n-1}^i * nums[i] \right) \mod 10$$
其中$C_{n-1}^i$是从n-1个元素选i个的组合数。因为10不是质数，计算组合数模10的时候可以分别计算模2、模5的结果，再通过中国剩余定理合并得到最终值，这种方法时间复杂度为O(n)，在n规模达到1e5以上时比模拟法优势明显。

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