無重復(fù)字符的最長(zhǎng)子串
難度：中等
描述：
給定一個(gè)字符串舀锨，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度玫恳。
樣例：
- 輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"穷吮，所以其長(zhǎng)度為 3预吆。
- 輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"鳞绕，所以其長(zhǎng)度為 1失仁。
- 輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3们何。
- 輸入: "dvdf"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "vdf"萄焦，所以其長(zhǎng)度為 3。
- 輸入: "asjrgapa"
輸出: 6
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "sjrgap"冤竹，所以其長(zhǎng)度為 6拂封。
- 輸入: "aabaab!bb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "ab!"，所以其長(zhǎng)度為 3鹦蠕。
- 輸入: "abcb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"冒签，所以其長(zhǎng)度為 3。
- 輸入: "asljlj"
輸出: 4
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "aslj"钟病，所以其長(zhǎng)度為 4萧恕。
- 輸入: "qwnfenpglqdq"
輸出: 8
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "fenpglqd"，所以其長(zhǎng)度為 8肠阱。
思路分析：
關(guān)鍵在于在出現(xiàn)重復(fù)字符時(shí)票唆，如何更新不重復(fù)字符的index
代碼模板：
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
}
想
一
想
再
看
答
案
代碼：
- 用對(duì)象儲(chǔ)存字符的位置, 出現(xiàn)重復(fù)字符時(shí)更新不重復(fù)字符的index。
var lengthOfLongestSubstring = function (s) {
let obj = {}; // 用于儲(chǔ)存字符出現(xiàn)的位置
let res = 0; // 最大值
let j = 0; // 不重復(fù)字符的index
for (let i = 0; i < s.length; i++) {
// 當(dāng)前值是否在對(duì)象中存儲(chǔ)過
const value = obj[s[i]]
if (value !== undefined) {
// 更新上一次重復(fù)值的index
// value + 1 跳過之前重復(fù)的字符
// j: 之前不重復(fù)的index 重復(fù)字符 需要全部跳過
j = Math.max(value + 1, j)
}
// 每個(gè)字符都計(jì)算一下最長(zhǎng)不重復(fù)值 保存最大值
// 不重復(fù)最長(zhǎng)長(zhǎng)度 = 當(dāng)前index - 上一次重復(fù)值的index + index從0開始 長(zhǎng)度從1開始
res = Math.max(res, i - j + 1);
// 存/更新 字符串index
obj[s[i]] = i
}
return res;
};
- 從左到右屹徘，一個(gè)字符一個(gè)字符搜索走趋，看是否重復(fù)。
var lengthOfLongestSubstring = function (s) {
var i = 0, // 不重復(fù)字符的index
res = 0; // 更新無重復(fù)字符的長(zhǎng)度
for (j = 0; j < s.length; j++) {
// 查找：不重復(fù)字符-當(dāng)前index之間 有沒有出現(xiàn)當(dāng)前字符
let index = s.slice(i, j).indexOf(s[j])
if (index === -1) {
// 更新無重復(fù)字符的長(zhǎng)度：當(dāng)前index-不重復(fù)字符的index + 長(zhǎng)度從1開始算
res = Math.max(res, j - i + 1);
} else {
// 更新i = 不重復(fù)字符的index
// 不重復(fù)字符的index = 原不重復(fù)的字符index + i-j中出現(xiàn)重復(fù)字符的index + 跳過該重復(fù)字符
i = i + index + 1;
}
}
return res;
};
