題目：
力扣原題鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
解題：
方法一：利用vector容器
執行用時 :20 ms, 在所有 cpp 提交中擊敗了66.62%的用戶
記憶體消耗 :9.6 MB, 在所有 cpp 提交中擊敗了85.78%的用戶
方法二：雙指標滑動
執行用時 :4 ms, 在所有 cpp 提交中擊敗了99.47%的用戶
記憶體消耗 :9 MB, 在所有 cpp 提交中擊敗了95.92%的用戶
方法一
對每一個傳入字串的字符與vector中的所有內容進行比較，無重復則將字符存入vector末尾，有重復則先更新不重復字串最大值mlen，再將vector中的重復字符即其之前的內容刪掉，回傳mlen，
vector的erase函式洗掉向量中[first,last)中元素：iterator erase(iterator first,iterator last)，注意引數是iterator型別，不能用數值，應使用vector的一個函式：iterator begin()，回傳向量頭指標，指向第一個元素，
vector的相關內容可參考：https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
class Solution { public: int lengthOfLongestSubstring(string s) { int n=s.length(); vector<char>str; int mlen=0; //掃描string s for(int i=0;i<n;i++){ char c = s[i]; //掃描vector str for(int m=str.size()-1;m>=0;m--){ if(c==str[m]){ //更新mlen if(mlen<str.size()) mlen = str. //洗掉重復字符及其之前的字符，用vector的begin（）函式控制洗掉區間 str.erase(str.begin(),str.begin()+m+1); break; } } str.push_back(c); } if(mlen<str.size()) mlen=str.size(); return mlen; } };
方法二
在s的字符數量大于等于2個的時候，用頭指標、尾指標指標分別指向s的開頭和其開頭+1，掃描兩指標之間的字符并與尾指標進行對比，根據對比情況移動指標，
這期間只有兩種情況，1：范圍[頭,尾)之間有跟尾字符重復的字符；2：沒有，
遇到情況1時，更新最大長度mlen，頭指標指向重復字符的后一位置，尾指標后移一位，繼續掃描對比，
遇到情況2時，頭指標不動，尾指標后移，繼續，
class Solution { public: int lengthOfLongestSubstring(string s) { int length=s.length(); //字串長度為0、1時直接回傳數字，雙指標沒有地方指， if(!length) return 0; if(length==1) return 1; //頭指標p，最大長度mlen至少為1， int p=0,mlen=1; //尾指標end for(int end=1;end<length;end++){ for(int aim=p;aim<end;aim++){ //情況1 if(s[aim]==s[end]){ //更新頭指標p p=aim+1; //更新最大長度mlen if(mlen<(end-aim)) mlen=end-aim; break; } } //情況2，要算上尾指標所以+1， if(mlen<end-p+1) mlen=end-p+1; } return mlen; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139450.html
標籤：其他
上一篇：數論篇4——逆元（數論倒數）
下一篇：演算法題--回文數