對應letecode鏈接：
力扣
題目描述：
給定一個字串 s ，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
示例 4:輸入: s = ""
輸出: 0提示：
0 <= s.length <= 5 * 104
s 由英文字母、數字、符號和空格組成
解題思路：
我們利用i,j指標持續維護我們的“視窗”，我們保證視窗內不含有重復字符，回圈開始時，j=i+1，回圈中，j不斷前移，視窗的長度“變長”，而i則根據視窗內是否有重復字符而控制視窗的長度，滑動視窗本質上就是一種列舉方式，列舉對于i的各種取值，子串所能取到的最大長度，但是這種列舉前后有相關性，因為我們只用考慮視窗元素的“進去”，大大減少了列舉次數，
j指標開始往后移動一直到出現重復字符或者到了字串的長度就停止移動
此時無重復字串的長度為j-i也就是3下一次i就從b開始
j指標開始移動
此時無重復字符的字串長度依然為j-i也就是3然后i在加加再次往后重復上述步驟在遍歷的程序中我們只需要定義一個遍歷maxlen記錄最大無 重復字符字串的長度即可
那么我們如何判斷是否重復呢？我們只需要使用一個哈希表記錄即可，在下一次遍歷之前將其清空即可
對應代碼：
class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.size(); int maxLen=0;//記錄最長出現的字符 unordered_set<char>tmp;//保存出現的字符 for(int i=0;i<n;i++){ tmp.insert(s[i]); int j=0; for(j=i+1;j<n;j++){ if(tmp.count(s[j])){//如果已經出現重復的直接跳出程式 break; }else{ tmp.insert(s[j]);//沒有重復則繼續插入 } } //記錄最大無重復字串的長度 if(j-i>maxLen){ maxLen=j-i; } tmp.clear();//清空容器 } return maxLen; } };
但是這樣的時間復雜度是0(N^2) 有沒有時間復雜度為O(N)的方法呢？我們可以使用一個陣列記錄字符出現的位置
假如我們有這們一個字串串我要求以a結尾無重復字串的長度我們只需要看此時看i減去i下標對應的字符上次出現的位置和對應以i-1對應字符結尾的無重復字符的長度+1兩者取最小值即可，可能有老鐵不太明白是什么意思馬上就解釋
這個字串如果我們要求 以i下標對應字符結尾的最大無重復字符的長度我們首先看i下標對應的字符為a他上次出現的位置為1號位置i為4而以i-1下對應字符結尾的最大無重復字串的長度為4但是先加入的a已經在對應已i-1下標結尾的最大無重復字串中出現過了所以以i位置結尾的最大無重復字符的字串的長度為4-1=3；也就是兩者取最小值
我們再來看這一種情況：
我們可以發現i上次出現的位置為0號位置i為4號位置而已i-1對應字符結尾的最大無重復字符的字串長度為2為什么不能夠更長了只有可能是出現了重復字符此時i-0=4-0=4而以i-1下標對應字符結尾的最大無重復字串的長度+1為3兩者取最小值即為3也就是以i下標對應字符結尾的最大無重復字符字串的最大長度，在上述程序中我們只需要定義一個變數maxLen記錄整個 字串中最長無重復字符字串的最大長度即可
對應代碼：
class Solution { public: int lengthOfLongestSubstring(string s) { if(s.size()==0){ return 0; } int arr[256]={0}; for(int i=0;i<256;i++){//沒有開始之前全部填成-1； arr[i]=-1; } arr[s[0]]=0;//第一個字符無重復字符字串的長度為0 int preMaxlen=1;//對應以i-1對應字符結尾無重復字符字串的長度 int MaxLen=1;//記錄最大長度 for(int i=1;i<s.size();i++){ preMaxlen=min(i-arr[s[i]],preMaxlen+1); if(preMaxlen>MaxLen){ MaxLen=preMaxlen; } arr[s[i]]=i; } return MaxLen; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/387953.html
標籤：其他
上一篇：《C語言深度剖析》第四章 指標和陣列 p2 C語言從入門到入土（進階篇）
下一篇：呼叫百度AI實作人像分割（下）