minSubArrayLen代码时间复杂度O(n)及循环复杂度判定问询

核心结论 #

这段求解长度最小子数组的代码整体时间复杂度为O(N)，属于典型的同向双指针（滑动窗口）实现。 #

内层while循环的复杂度说明 #

不要孤立看单次外层循环触发内层循环的执行次数：

• 内层循环不是严格的单次O(1)：极端场景下单次触发内层循环可能执行多次移动操作，比如当数组前序所有元素累加后才第一次达到target值时，内层循环可能连续移动left指针多次。
• 从全局执行总次数看，内层循环的总执行次数永远不会超过N次：因为left指针初始值为0，整个运行过程中只会向右移动，永远不会向左回退，最多从0移动到数组末尾位置n，累计移动次数上限就是n。
  摊还到每一次外层循环的迭代中，内层循环的平均执行次数是常数级，这也是很多人会误以为内层是O(1)的原因。

循环时间复杂度的判定规则 #

不管是for循环还是while循环，判定复杂度的核心依据从来不是嵌套层数，而是循环内操作的全局总执行次数：

• 如果循环内所有操作的总执行次数，和输入规模N呈线性正相关，且没有更高阶的增长关系，这部分循环贡献的复杂度就是O(N)。比如最常见的单层遍历数组的for循环，总执行n次，就是O(N)；如果是两层嵌套循环，外层跑n次、内层每次都从头开始跑n次，总次数是n²，就是O(N²)。
• 如果无论输入规模N增长到多大，循环内操作的总执行次数始终不超过一个和N无关的固定常数，这部分循环的复杂度就是O(1)。比如某个while循环固定最多跑3次就会退出，和输入长度没关系，那就是O(1)。
• 针对双指针类题目特别注意：只要两个指针都保持单向移动、全程不发生回退，不管写了几层循环，两个指针的总移动次数上限都是2N，整体复杂度一定是O(N)，不要看到两层循环就误判为O(N²)。

附：题面原代码 #

int minSubArrayLen(int target, vector<int>& nums)
{
    int left=0;
    int right=0;
    int n=nums.size();
    int sum=0;
    int ans=INT_MAX;
    int flag=0;
    while(right<n)
    {
        sum+=nums[right];
        if(sum>=target)
        {
            while(sum>=target)
            {
                flag=1;
                sum=sum-nums[left];
                left++;
            }
            ans=min(ans,right-left+2);
        }
        right++;
    }
    if(flag==0)
    {
        return 0;
    }
    return ans;
}

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