leetcode 209 滑动窗口解题时间复杂度为什么是O(n):!!!看最内层循环的执行频度

2023-12-29 12:24:33

209. 长度最小的子数组 - 力扣（LeetCode）

题解：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

?时间复杂度：看频度最高的语句执行的次数

基本语句：找出语句频度最大的那条语句作为基本语句

计算基本语句的频度得到问题规模的某个函数f(n),取其数量级，用O表示

时间复杂度由嵌套最深层的语句的频度决定

本题基本语句关键代码

for(last=0;last<nums.size();last++)
        {
            sum+=nums[last];
            while(sum>=target)
            {
                tmp_re=last-sta+1;
                if(tmp_re<result)
                {
                    result=tmp_re;
                }
                sum-=nums[sta];
                sta++;             
            }
        }

while中的语句即基本语句，其最多只能执行n次(最坏情况sta一直加加到末尾),所以时间复杂度是O(n)?

文章来源:https://blog.csdn.net/2301_81198610/article/details/135213815
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。