崔憨憨 2021-12-17 11:30 采纳率: 100%
浏览 562
已结题

请问为什么for中嵌套while循环 时间复杂度却还是O(n)呢

```
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int result = Integer.MAX_VALUE;
int sum = 0;
for(int right = 0; right < nums.length; right++){
sum += nums[right];
while(sum >= target){
result = Math.min(result, (right - left + 1));
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}

```java

img


没太懂这句话的意思 可以帮忙分析一下吗

  • 写回答

1条回答 默认 最新

  • 俺不理解 2021-12-17 11:52
    关注

    外层更新变量是 right,right范围是 0 ~ len - 1
    内层更新变量是 left,left范围也是 0 ~ len - 1。
    两者无相关性,也就是说 right 更新时,left不会从零开始,right 只会遍历一遍,left也只会一遍,所以复杂度是 2 * n,及 O(n)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 12月25日
  • 已采纳回答 12月17日
  • 创建了问题 12月17日

悬赏问题

  • ¥15 preLaunchTask"C/C++: aarch64- apple-darwin22-g++-14 生成活动 文件”已终止,退出代码为-1。
  • ¥18 关于#贝叶斯概率#的问题:这篇文章中利用em算法求出了对数似然值作为概率表参数,然后进行概率表计算,这个概率表是怎样计算的呀
  • ¥20 C#上传XML格式数据
  • ¥15 elementui上传结合oss接口断点续传,现在只差停止上传和继续上传,各大精英看下
  • ¥100 单片机hardfaulr
  • ¥20 手机截图相片分辨率降低一半
  • ¥50 求一段sql语句,遇到小难题了,可以50米解决
  • ¥15 速求,对多种商品的购买力优化问题(用遗传算法、枚举法、粒子群算法、模拟退火算法等方法求解)
  • ¥100 速求!商品购买力最优化问题(用遗传算法求解,给出python代码)
  • ¥15 虚拟机检测,可以是封装好的DLL,可付费