LeetCode长度最小子数组Python实现超时问题咨询

本题为经典算法题，题目要求：给定由n个正整数组成的数组以及正整数target，查找元素和大于等于target的连续子数组的最小长度；若不存在符合条件的子数组则返回0。

问题复现 #

原有实现代码如下：

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        start_idx = 0
        end_idx = 0
        min_len = float('inf')

        while end_idx < len(nums):
            if sum(nums[start_idx:end_idx + 1]) < target:
                end_idx += 1
            else:
                min_len = min(end_idx - start_idx + 1, min_len)
                start_idx += 1
        return 0 if min_len == float('inf') else min_len

该代码在小规模数组上可正常运行，但处理大规模数组时会触发Time Limit Exceeded（超出时间限制）报错，无法通过长度较大的测试用例。

超时根因 #

性能瓶颈就在sum(nums[start_idx:end_idx + 1])这行语句：

• 切片操作nums[start_idx:end_idx + 1]会先拷贝生成一个新的子列表，带来额外的内存分配、元素拷贝开销
• sum()函数会遍历整个新生成的子列表逐元素累加，每次求和的时间复杂度是O(k)，k为当前滑动窗口的长度

整体来看，原本滑动窗口算法的时间复杂度应该是O(n)（每个元素最多被左右指针各访问一次），但因为每次窗口调整都重新遍历整个窗口求和，代码实际时间复杂度退化为O(n²)，当数组长度达到几万、几十万量级时，总运算量会远超时间限制，必然超时。

优化方案 #

核心思路是维护一个单独的当前窗口和变量，避免重复计算整个窗口的累加和：

• 右指针向右移动、有新元素进入窗口时，直接把新元素的值加到当前和上
• 左指针向右移动、有元素移出窗口时，直接把移出元素的值从当前和上减掉

优化后的代码如下，时间复杂度稳定为O(n)，无额外的切片拷贝开销：

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        start_idx = 0
        min_len = float('inf')
        current_sum = 0

        for end_idx in range(len(nums)):
            current_sum += nums[end_idx]
            # 窗口和满足要求时，持续收缩左边界找最小长度
            while current_sum >= target:
                min_len = min(min_len, end_idx - start_idx + 1)
                current_sum -= nums[start_idx]
                start_idx += 1
        
        return 0 if min_len == float('inf') else min_len

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