3. 無重復字符的最長子串

難度中等3341

給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。

示例?1:

輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是?"wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。

思路：遍歷字符串，利用hash表判斷有無重復字符，同時更新最長子串長度max，如果有重復字符則找到重復字符的位置i，然后更新index起始位置為i+1(重復字符前面的字符都不用再參與計算了，包含他們的最長子串都不超過當前max)

class Solution { public:int lengthOfLongestSubstring(string s) {map<char,int> hash;int result = 0;int index = 0;for(int i=0;i<s.length();++i){//如果找到重復的，并且這個重復值的index大于等于上一重復值索引，那么就去更新indexif(hash.find(s[i])!=hash.end() && hash[s[i]]>=index)index = hash[s[i]]+1;result = max(i-index+1,result);hash[s[i]] = i;}return result;} };

?

總結

以上是生活随笔為你收集整理的最长不重复子串—leetcode3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。