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

代码导航 论文问答 1
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 ```

回复

共1条回复 我来回复
  • 源码工坊
    这个人很懒,什么都没有留下~
    评论

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

    0条评论

发表回复

登录后才能评论