題目
給定一個字符串?s?，請你找出其中不含有重復字符的?最長?子串?的長度。
示例?1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: s = "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是?"wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。
滑動窗口技術
思路：
這道題主要用到思路是：滑動窗口
什么是滑動窗口？
其實就是一個隊列,比如例題中的 abcabcbb，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！
如何移動？
我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！
一直維持這樣的隊列，找出隊列出現最長的長度時候，求出解！
時間復雜度：O(n)
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:if not s:return 0left = 0lookup = set()n = len(s)max_len = 0cur_len = 0for i in range(n):cur_len += 1while s[i] in lookup:lookup.remove(s[left])left += 1cur_len -= 1if cur_len > max_len:max_len = cur_lenlookup.add(s[i])return max_len這段代碼使用滑動窗口技術來找出字符串中最長的無重復字符子串的長度。以下是逐行解釋：
-
if not s: return 0
檢查輸入字符串是否為空，如果為空則直接返回0。 -
left = 0
初始化左指針left為0，表示當前窗口的起始位置。 -
lookup = set()
創建一個空集合lookup，用于記錄當前窗口中的字符。 -
n = len(s)
計算字符串s的長度，并賦值給變量n。 -
max_len = 0
初始化最長子串長度max_len為0。 -
cur_ len = 0
初始化當前窗口長度cur_ len為0。 -
for i in range(n):
遍歷字符串中的每一個字符，索引為i。 -
cur_ len +=1
進入循環后，先將當前窗口長度增加1，假設當前字符可以加入窗口。 -
while s[i] in lookup:
檢查當前字符s[i]是否已經在當前窗口中存在。如果存在，則需要調整窗口左邊界：a.?lookup.remove(s[left])
移除集合中的左指針指向的字符，表示該字符不再屬于當前窗口。b.?left +=1
將左指針向右移動一位，縮小窗口范圍。c.?cur_ len -=1
由于移除了一個字符，當前窗口長度減1。 -
if cur_ len > max_len: max_len = cur_ len
檢查當前窗口長度是否為最大值，并更新max_len。 -
lookup.add(s[i])
將當前字符s[i]添加到集合中，表示該字符已加入當前窗口。 -
return max_len
遍歷結束后，返回最長無重復子串的長度max_len。
#include<string.h> //首先額外引入一個新的字符串庫
int lengthOfLongestSubstring(char* s) {int len=strlen(s); //得到字符串的長度int i = 0; //i是循環變量,從第一個字符開始找最長的無重復字母的子串int result = 0; //result 為最后的返回的結果,求長度最長時，result至為0;求長度最短時，result至為INT32_MAXint count = 0; //count 為每次循環的最長的無重復字母的子串的長度int b; //b 為遞歸調用循環變量while (s[i]){int flag = 1; //flag 為標志變量，首先至為1int j; //里層循環的變量jfor (j = 0; j < i; j++){if (s[i] == s[j])//如果找到重復的的字母，那么就{flag = 0; //標志變量至為0b = j; //遞歸變量b賦值為j,即在子串的與s[i]重復的第一個字母break; //跳出里層循環}}if (flag == 1)//如果遍歷了一遍，如果沒發現重復的字母，flag還是等于1{i++; count++; //子串的長度加1result = result > count ? result : count; //更新result的結果:count和原來result中最大的數}else{break; //否則，退出外層循環}b = i; //如果i=1時,s[i](即s[b],即s[1])和s[1]相同時，遞歸時直接往后移一位就行；；當i>1,也是從子串的與s[i]重復的第一個字母s[b]下一個字母————s[b+1]開始,}// 設置遞歸出口條件if (b+1<len) //注意不建議*(s+b+1),這樣算是空指針解引用，在力扣上報錯了,但在VS上沒報錯 //所以必須保證b+1<len{count = lengthOfLongestSubstring(s+b+1);result = result > count ? result : count;//必須要有這一步，否則也會出錯//將遞歸的結果與上級函數的result比較}return result;
}
_39)
