木又同學2020年第3篇解題報告
leetcode第3題：無重複字元的最長子串
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" 是一個子序列，不是子串。
複制
【思路】
可以暴力求解，對于每一個子串，判斷是否有重複字元。判斷是否有重複字元，需要O(n)，是以總的時間複雜度為O(n^3)
我們想想，有很多子串是沒有必要判斷的，比如對于"dvdf"，當知道“dvd”是重複子串時，“dvdf”肯定是重複子串。是以，我們使用i表示非重複子串起始下标，j用于周遊數組，當s[j]存在于s[i:j]中，說明s[i:j+1]是重複子串，s[i:j]是以i為起點的最長非重複子串，然後更改i為s[i:j]中與s[j]相同的元素的下标。
【代碼】
python版本
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 視窗i->j
i = 0
res = 0
for j in range(i+1, len(s)):
# 如果有重複字元，比較res和前一段非重複字元串長度，并更改i
if s[j] in s[i:j]:
res = max(res, j-i)
i += s[i:j].index(s[j]) + 1
# 不要忘了，最後要比較res和len(s)-i
res = max(res, len(s)-i)
return res
複制
C++版本
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0;
int res = 0;
for (int j=i+1; j < s.size(); j++){
// s[i:j]中是否存在s[j]
// 存在比較長度，且更新i
int offset = s.substr(i, j-i).find(s[j]);
if (offset >= 0){
res = max(res, j-i);
i += offset + 1;
}
}
// 不要忽略最後一段子串
int tmp = s.size() - i;
res = max(res, tmp);
return res;
}
};
複制