問題：給定一個字串 s，找出不重復字符的最長子串的長度。
示例：輸入：s = "abcabcbb" 輸出：3 解釋：答案是“abc”，長度為 3。
我的解決方案：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set()
l = r = curr_len = max_len = 0
n = len(s)
while l < n:
if r < n and s[r] not in seen:
seen.add(s[r])
curr_len = 1
max_len = max(curr_len, max_len)
r = 1
else:
l = 1
r = l
curr_len = 0
seen.clear()
return max_len
我知道這不是一個有效的解決方案，但我無法弄清楚它的時間復雜度。
我訪問字串中的每個字符，但是，對于每個字符，視窗都會擴展，直到找到重復的字符。所以每個字符最終都會被多次訪問，但不確定是否有足夠的時間來證明 O(n 2 ) 時間復雜度是合理的，顯然，它比 O(n) 差得多。
uj5u.com熱心網友回復：
如果您知道您的輸入可以組成的字符集的大小，您可以聲稱該演算法是 O(n)，因為您的視窗可以擴展的長度受到在遇到重復之前您可以傳遞的不同字符的數量的限制，并且這受您正在使用的字符集的大小限制，它本身是一些與字串長度無關的常量。例如，如果您只使用小寫字母字符，則演算法為 O(26n) = O(n)。
更準確地說，你可以說它在 O(n*(min(m,n)) 中運行，其中 n 是字串的長度，m 是字串字母表中的字符數。 min 的原因是即使您以某種方式使用無限唯一字符的字母表，最壞的情況是您在字串末尾執行雙回圈。這意味著如果您可以在字串中遇到的可能字符數超過字串的長度，最壞的情況是 O(n^2) 性能（當字串的每個字符都是唯一的時會發生這種情況）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359129.html
上一篇：在Python中創建一個在特定條件下加起來為1的陣列
下一篇：如何合并滿足堆順序的兩棵樹？