下面是一个程序，它可以在给定字符串str的情况下，找到不包含重复字符的最长子字符串的长度。(详细信息(
int test(string str) {
int left = 0, right = 0, ans = 0;
unordered_set<char> set;
while(left < str.size() and right < str.size()) {
if(set.find(str[right]) == set.end()) set.insert(str[right]);
else {
while(str[left] != str[right]){
set.erase(str[left]);
left++;
}
left++;
}
right++;
ans = (ans > set.size() ? ans : set.size());
}
return ans;
};
上述解决方案的时间复杂度是多少？是O(n^2(还是O(n(，其中n是字符串的长度？
请注意，我已经在网上浏览了多个问题，也读到了关于大哦的文章，但我仍然很困惑。对我来说，由于两个while循环，它看起来像O(n^2(的复杂性，但我想从这里的专家那里得到证实。
平均为O(n(。
您在这里看到的是一种滑动窗口技术(具有可变窗口大小，也称为"双指针技术"(。
是的，有两个循环，但如果你看，这两个循环中任何一个的任何迭代都会增加其中一个指针(left或right(。在第一个循环中，要么调用第二个循环，要么不调用，但每次迭代都会增加right。第二个循环总是增加left。
left和right都可以具有不同的n值(因为当right >= n或left == right时两个循环都将停止(。因此，第一个循环将具有n执行(从0到n-1的right的所有值(，而第二个循环最多可以具有n执行(left的所有可能值(，这是2n = O(n)执行的最坏情况。
最坏情况复杂性
为了完整起见，请注意，我平均写了O(n(。原因是CCD_ 17的复杂度平均为O(1(，但在最坏的情况下为O(n(。set.erase也是如此。原因是unordered_set是用哈希表实现的，在所有项目都在同一个bucket中的情况下，它需要迭代所有项目。
因此，即使我们有O(n(次循环迭代，有些迭代也可能是O(n(次。这意味着在一些非常不可能的情况下，执行可能会上升到O(n^2(。你真的不应该担心，因为发生这种情况的概率接近0，尽管我不知道C++中char的哈希技术是什么，但我敢打赌，我们永远不会把所有字符都放在同一个桶中。