找到給定字符串中最長的沒有重復(fù)的子字符串爱态。
例子：
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
我的o(n^2)算法：
讓left = 0未状，right = 0，maxlenght = 0茁帽，然后right依次向后掃描，建一個dictionary绸吸，key為掃描過的字符媳搪，value為位置，如果沒有right指向的字符沒有在dictionary里面瞧毙，就放進(jìn)去然后right繼續(xù)向后胧华，如果在dictionary里面則將left指定到重復(fù)字符位置+1， 重新調(diào)整dictionary宙彪， 直到right到達(dá)最??矩动。
python代碼：
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
res = 0
left = 0
right = 0
hashset = {}
while right < len(s):
while right < len(s) and s[right] not in hashset:
hashset[s[right]] = right
right += 1
if right < len(s) and s[right] in hashset:
if hashset[s[right]] >= left:
res = max(res, right-left)
left = hashset[s[right]] + 1
hashset[s[right]] = right
right += 1
res = max(res, right-left)
return res
看別人的o(n)算法，太厲害了吧释漆。
設(shè)置start和maxlength都為0悲没，useddict 為用過的字符。for loop從左向右循環(huán)男图，如果字符在dictionary里沒出現(xiàn)過示姿，則更新maxlength，如果字符在dictionary中出現(xiàn)過逊笆，并且start在字符位置之前栈戳，那么更新start在出現(xiàn)字符之后一位。
python代碼：
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = maxlength = 0
useddict = {}
for i in range(len(s)):
if s[i] in useddict and start <= useddict[s[i]]:
start = useddict[s[i]] + 1
else:
maxlength = max(maxlength, i - start + 1)
useddict[s[i]] = i
return maxlength
