給定一個字符串脆粥,請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc",所以其長度為 3意述。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b",所以其長度為 1吮蛹。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"欲险,所以其長度為 3。
請注意匹涮,你的答案必須是 子串 的長度,"pwke" 是一個子序列槐壳,不是子串然低。
解題思路:
優(yōu)化的滑動窗口
上述的方法最多需要執(zhí)行 2n 個步驟。事實上务唐,它可以被進一步優(yōu)化為僅需要 n 個步驟雳攘。我們可以定義字符到索引的映射,而不是使用集合來判斷一個字符是否存在枫笛。 當(dāng)我們找到重復(fù)的字符時吨灭,我們可以立即跳過該窗口。
也就是說刑巧,如果 s[j] 在 [i, j) 范圍內(nèi)有與 j′重復(fù)的字符喧兄,我們不需要逐漸增加 i。 我們可以直接跳過 [i啊楚,j'] 范圍內(nèi)的所有元素吠冤,并將 i變?yōu)?j' + 1。
var lengthOfLongestSubstring = function(s) {
let n = s.length;
let ans = 0;
let map = {}
for(let j=0,i=0;j<n;j++)
{
if(map.hasOwnProperty(s[j]))
{
i =Math.max(map[s[j]],i);
}
ans = Math.max(ans,j-i+1);
map[s[j]] = j+1
}
return ans;
};