c++ - 时间复杂度是 O(n) 而不是 O(n^2)？

Question

我正在解决关于 LeetCode.com 的问题:

Given a vector nums of positive integers, count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

代码(我在大量在线帮助下编写的)如下:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(nums.empty() || k<=1) return 0;

        int counter=0, left=0, currProd=1;
        for(int i=0; i<nums.size(); i++) {
            currProd*=nums[i];
            while(left<nums.size() && currProd>=k)
                currProd/=nums[left++];
            counter+=i-left+1;
        }

        return counter;
    }
};

虽然我明白发生了什么，但我不明白为什么说时间复杂度是 O(n) 而不是 O(n^2)。恕我直言，i 和 left 都递增，导致在最坏的情况下访问 nums 的每个元素两次 - 一次由归纳变量 i 然后 left。

那么，时间复杂度O(n)如何？

Answer 1

虽然代码可能看起来像O(N^2)，但要注意的关键是:

Inside the for-loop, left is never reset to 0, and is always incremented in the while-loop.

这意味着while 循环在代码的整个 执行期间最多只能执行N 次。因此代码只遍历数组两次，因此 O(N)。