尋找最長的不含有重復(fù)字符的子串
可能看標(biāo)題不會明白這個(gè)題到底什么意思，來看看下面的例子：
abcabcbb ? abc ? 3
bbbb ? b ? 1
pwwkew ? wke ? 3
看了栗子是不是明白了呢峰伙？
其實(shí)需求很簡單疗疟，實(shí)現(xiàn)的方法也很多，不過在這里我要來寫一種效率最高的算法瞳氓，只需要一次循環(huán)就可解決：
function findNoRepeatMaxLenStr (str) {
let lastPositions = {}
let start = 0
let maxLen = 0
for (let i=0; i<str.length; i++) {
const s = str[i]
if (lastPositions[s] !== 'undefined' && lastPositions[s] >= start) {
start = lastPositions[s] + 1
}
if (i - start + 1 > maxLen) {
maxLen = i - start + 1
}
lastPositions[s] = i
}
return maxLen
}
// test
console.log(findNoRepeatMaxLenStr('abcabcbb')) // 3
那么看完代碼策彤，請自己先胡思亂想一下，能看得懂不？
行了店诗，看到這我就知道你沒看懂裹刮，那么來解釋一下吧。
思路是這樣的必搞，假如下面的圖形是一個(gè)字符串必指，每個(gè)格子代表一個(gè)字符：
此時(shí)咱們開始使用 for 循環(huán)掃描整個(gè)字符串，當(dāng)掃描到 x（x 代表任意位置的任意的字符串）的時(shí)候恕洲，那么咱們應(yīng)該怎么做呢塔橡？
首先要記錄一個(gè) start 起始位置，當(dāng)然一開始就是 0 了霜第，那么 start 在循環(huán)中不僅僅只是表示字符串從 0 開始葛家，還表示當(dāng)前不含有最長重復(fù)子串的開始，那么咱們要做的事情就一件：保證從 start 到 x 之間沒有重復(fù)的字符串泌类，再說的通俗點(diǎn)就是看檢查 start 到 x 之間有沒有重復(fù)的 x 癞谒。
那么怎么做到檢查這個(gè)動作呢?
這個(gè)時(shí)候 lastPositions 就派上用場了。當(dāng)循環(huán)到 x 的時(shí)候刃榨，記錄一下這個(gè) x 最后一次出現(xiàn)的位置在哪里弹砚。
那么記錄完畢之后，當(dāng)進(jìn)行檢查 start 到 x 之間 是否有重復(fù)的 x 的時(shí)候枢希，咱們就去問 lastPositions[x]桌吃，此時(shí)會有2種情況：
第一種情況是 x 從來沒有出現(xiàn)過或者出現(xiàn)在了 start 之前；
第二種情況是 x 出現(xiàn)在 start 到 x 中間苞轿。
那么對于第一種情況茅诱，咱們不用去管。而第二種情況自然是不滿足條件的情況了搬卒，此時(shí)瑟俭，咱們就要更新 lastPositions[x]，將這個(gè) x 的位置更新為 lastPositions[x] + 1契邀。
總結(jié)下來就是：
lastPositions[x] 不存在或 < start 滿足條件摆寄，無需操作
lastPositions[x] 存在并且 >= start 不滿足條件，更新 lastPositions[x]++
那么在結(jié)合上面的代碼蹂安，邏輯就清晰了椭迎，唯一有些繞圈圈的地方就是第二個(gè) if 中的 +1 操作，原因就是字符串的索引是從 0 開始的田盈，那么假如第一個(gè)為 x 滿足條件畜号，實(shí)際索引是0，那么長度應(yīng)該是 0 + 1 = 1允瞧。
最后简软，這道算法題的出處來自：
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
里面有各種各樣的實(shí)現(xiàn)方法蛮拔，可以作為參考。
覺得本文對你有幫助痹升？請分享給更多人
