smallestSubWithSum双循环代码时间复杂度是O(n²)还是O(n)？

你提交的代码如下：

def smallestSubWithSum(self, a, n, x):
    min1 = float('inf')
    i = 0
    while (i < n):
        if a[i] > x :
            return 1
        else:
            sum1 = a[i]
            j = i + 1
            
            while (j < n):
                sum1 += a[j]
                
                if sum1 > x:
                    m = j - i + 1
                    min1 = min(m,min1)
                    break
                else:
                    j +=1
            i +=1
    return min1

核心结论 #

• 严格意义上，这段代码的最坏时间复杂度为O(n²)
• 本次提交能通过平台O(n)时间要求，是平台测试用例特性导致的运行表现符合要求，不代表代码本身是严格O(n)复杂度

原理说明 #

最坏场景推导 #

我们可以构造出让这段代码运行次数达到O(n²)的输入：比如数组所有元素都是1，x等于数组长度n。这种场景下：

• 对每个左端点i，内层循环的j都需要从i+1一直走到数组末尾n-1，才能让累加和大于x
• 总运行次数为 n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，符合O(n²)的复杂度特征

能通过平台测试的原因 #

「和大于x的最小长度子数组」是经典的正数数组滑动窗口问题，大部分OJ平台的测试用例都符合两个特征：

1. 数组所有元素都是正整数
2. 满足条件的子数组平均长度非常短
   这种场景下你的代码内层循环几乎每次只需要执行1~3次就会触发break，总运行次数和严格O(n)的标准滑动窗口解法差异极小，平台的时间限制阈值一般会留有余量，所以会判定为符合时间要求。

优化为严格O(n)的方案 #

如果要得到严格O(n)的实现，可以修改为标准滑动窗口写法，让右指针j永远不回退：

def smallestSubWithSum(self, a, n, x):
    min_len = float('inf')
    current_sum = 0
    left = 0
    for right in range(n):
        current_sum += a[right]
        while current_sum > x:
            min_len = min(min_len, right - left + 1)
            current_sum -= a[left]
            left += 1
    return min_len if min_len != float('inf') else 0 # 可根据题目要求调整不存在的返回值

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