c++ - 带内部while循环的while循环:O(n)或O(n ^ 2)？

#include <unordered_map>
using namespace std;

        int lengthOfLongestSubstring(string s) {

            unordered_map<char, int> ht;
            int max = 0;

            int i = 0; int j = 0;
            while (i < s.size() && j < s.size()) {

                if (ht.find(s.at(j)) == ht.end()) {
                    ht.insert( {s.at(j), j} );
                    max = (j - i + 1 > max) ? j - i + 1 : max;
                    j++;
                }
                else {
                    int len = ht.at(s.at(j)) + 1;
                    while(i < len) {
                        ht.erase(s.at(i));
                        i++;
                    }

                }

            }

            return max;
        }

时间复杂度是O(n)还是O(n^2)？为什么？
我的直觉是它是O(n)，i和j遍历相同的长度。

最佳答案

它的:

严格来说:O(2n)，在最坏的情况下，您迭代输入大小的两倍；

用渐近语言讲:O(n)，因为忽略常量因子is。

关于c++ - 带内部while循环的while循环:O(n)或O(n ^ 2)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/63123206/