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

请问为什么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日