如何解决Python刷LeetCode时出现的Time Limit Exceeded超时问题

你当前的实现采用双层循环遍历计算左右和，时间复杂度为O(n²)。题目给出的约束1 <= nums.length <= 10^4指数组长度最大为10000，此时*O(n²)*算法需要执行约10^8次运算，Python的运行效率无法在题目限定的时间内完成这么多次运算，因此触发Time Limit Exceeded报错。

你可以通过以下步骤提前预判算法是否会超时：

• 第一步提取题目给出的输入规模上限，本题输入规模上限为n=10^4
• 第二步计算你设计的算法的时间复杂度，不同时间复杂度对应的可通过输入规模参考：
  • O(n)：支持输入规模n≤10^6
  • O(nlogn)：支持输入规模n≤10^5
  • O(n²)：仅支持输入规模n≤10^3
• 只要你的算法复杂度对应的可通过上限低于题目给出的输入规模，就必然会触发TLE，需要优化算法逻辑降低时间复杂度。

可以利用数组总和推导右和，避免重复遍历计算，将时间复杂度降到O(n)：

1. 先计算数组所有元素的总和total
2. 遍历每个下标cur时，维护左和leftSum：即cur左侧所有元素的和
3. 此时右和可直接通过公式计算：rightSum = total - leftSum - nums[cur]
4. 比对leftSum和rightSum，相等就返回当前下标cur，否则把nums[cur]加到leftSum中继续遍历

优化后代码如下：

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0
        for cur in range(len(nums)):
            right_sum = total - left_sum - nums[cur]
            if left_sum == right_sum:
                return cur
            left_sum += nums[cur]
        return -1

你原思路的逻辑示意图：

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