Python寻找和为指定值的连续子数组代码问题及时间复杂度分析

一、时间复杂度严重超标（远达不到O(n)） #

这段代码最大的问题是循环内重复调用sum(arr[start:i+1])——每次求和都要遍历当前子数组的所有元素，时间复杂度为O(k)（k是当前子数组长度）。在最坏场景下，整体时间复杂度会退化为O(n²)，必然耗时过长：

• 典型场景：全正数数组如[1,1,1,...,1]（n个元素），目标值s=n-1。此时代码会反复遍历不同区间求和，总遍历次数为n+(n-1)+...+2 = O(n²)，当n达到1e4量级时，运行时间会急剧上升，甚至超时。

二、多处逻辑错误 #

• 前置判断完全错误：开头if sum(arr[0:n]) < s: return [-1]忽略了数组含负数的情况。例如arr=[1,-2,3]、s=3时，整个数组sum为2<3，但子数组[3]的sum恰好等于s，代码会直接返回-1，错失正确结果。
• 重复计算无意义：开头连续两次调用sum(arr[0:n])，完全可以计算一次存入变量，避免额外的O(n)开销。
• 循环结束后的判断无效：循环结束后通过sum_elements < s返回-1，但sum_elements仅代表最后一次循环的子数组和，无法覆盖所有可能的子数组情况，存在漏判。
• 边界场景未处理：当start超过i时，arr[start:i+1]是空数组，sum为0，若s=0会误判为符合条件，若s为正数则会进入错误分支。

三、O(n)时间复杂度的优化方案 #

要实现O(n)的滑动窗口解法，核心是维护当前子数组的和，避免重复计算，代码示例：

def subArraySum(self, arr, n, s):
    current_sum = arr[0]
    start = 0
    for i in range(1, n):
        current_sum += arr[i]
        # 当当前和超过目标值，收缩左边界
        while current_sum > s and start <= i:
            current_sum -= arr[start]
            start += 1
        # 找到符合条件的子数组
        if current_sum == s:
            return [start + 1, i + 1]
    # 检查单个元素的情况
    if arr[-1] == s:
        return [n, n]
    return [-1]

注：如果数组包含负数，滑动窗口法不再适用，此时需要用前缀和+哈希表的方法，通过存储前缀和的索引快速定位符合条件的子数组，同样可以达到O(n)时间复杂度。

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