原题地址：无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
暴力循环
通过暴力循环找出字符串所有可能的子串，并找出其中最长的符合要求的子串即可：
/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring1 = function(s) {
if (s.length < 2) {
return s.length;
}
// 判断子串是否符合要求
const isValid = (left, right) => {
let set = new Set(); // 利用Set判断有无重复字符
for (let i = left; i < right + 1; i ++) { // 注意右边界
if (set.has(s[i])) {
return false;
}
set.add(s[i]);
}
return true;
};
let max = 1; // 单字符子串都是符合要求的
for (let i = 0; i < s.length - 1; i ++) {
for (let j = i + 1; j < s.length; j ++) {
if (isValid(i , j)) { // 此时的子串长度为(j - i + 1)
max = Math.max(max, j - i + 1);
}
}
}
return max;
};
测试：
let start = new Date();
const test = lengthOfLongestSubstring1;
console.log(test('abcabdcbb')); // 4
console.log(test('bbbbb')); // 1
console.log(test('pwwkew')); // 3
console.log(test('au')); // 2
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 三重循环，时间复杂度为O($n^3$)
空间复杂度： 需要一个额外的set来辅助判断子串中是否有重复字符，set占据的空间不会超过字符串的长度，由于set会自动去重，所以也不会超过字符串所用字符集的长度。空间复杂度为O(min(m,n))，m和n分别是字符串和所用字符集的长度
滑动窗口
暴力循环法非常简单，但速度太慢，提交到LeetCode会超时。我们可以对它进行一些优化。
定义一个左闭右开的滑动窗口，初始化时滑动窗口内的子串是没有重复字符的。将窗口的右边界逐步向右移动，每移动一步就判断右边界所在的字符之前有没有出现过，如果出现过且 上一次出现就在滑动窗口内，则将窗口的左边界移动到该字符上一次出现的右侧，这样就可以保证窗口内的字符还是不会有重复。具体实现代码如下：
/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring2 = function(s) {
if (s.length < 2) {
return s.length;
}
let [left, max] = [0, 0]; // [滑动窗口的左边界，滑动窗口的最大长度]
let map = new Map(); // 用来记录出现过的每个字符及它最后一次出现的位置
for (let i = 0; i < s.length; i ++) {
// 定义[left, i)为滑动窗口，这个窗口内是没有重复字符的
if (map.has(s[i])) {
// 如果窗口右边界的字符之前出现过，就判断它最后一次出现是否在窗口内
// 如果是在窗口内，就将窗口的左边界移动到它最后一次出现位置的右侧
// 这样就能保证这个窗口内还是没有重复字符
left = Math.max(left, map.get(s[i]) + 1);
}
map.set(s[i], i); // 保存每个字符最后一次出现的位置
max = Math.max(max, i - left + 1);
}
return max;
};
测试：
let start = new Date();
const test = lengthOfLongestSubstring2;
console.log(test('abcabdcbb')); // 4
console.log(test('bbbbb')); // 1
console.log(test('pwwkew')); // 3
console.log(test('au')); // 2
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 只需要进行一次遍历，时间复杂度为O(n)
空间复杂度： 与暴力循环法相同， 为O(min(m,n))，m和n分别为字符串和字符集的长度
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019