字节&Leetcode3：无重复字符的最长子串

[sisterAn]

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

附leetcode：leetcode

[AiKunnnnn]

对原数组进行判断，是否在arr里 如果在就将arr字符串之前的全部去除，不在就直接push，最后判断长度

var lengthOfLongestSubstring = function(s) {
 let arr = [];
 let length = 0;
 for(let item of s){
 if(arr.includes(item)){
 let index = arr.indexOf(item);
 arr.splice(0,index+1);
 }
 arr.push(item);
 length = length > arr.length ? length : arr.length;
 }
 return length;
};

[Aiyoweioo]

快慢指针维护一个滑动窗口，如果滑动窗口里面有快指针fastp所指向的元素（记录这重复元素在滑动窗口的索引tmp），那么滑动窗口要缩小，即慢指针slowp要移动到tmp的后一个元素。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
 let res = 0, slowp = 0, tmp = 0
 for(let fastp = 0; fastp < s.length; fastp++) {
 tmp = s.substring(slowp,fastp).indexOf(s.charAt(fastp)) // 滑动窗口有没有重复元素
 if(tmp === -1) { // 没有
 res = Math.max(res, fastp-slowp+1) // 上一次值和滑动窗口值大小比较
 }else{ // 有，移动慢指针， 是slowp+tmp+1不是tmp+1，因为tmp是根据滑动窗口算的
 slowp = slowp + tmp + 1
 }
 }
 return res
};

细节： 快指针也要从0开始，如果从1开始，类似'aaaa'，结果就是0，因为tmp永远不等于-1

[fanefanes]

方法一：悬浮框圈出满足条件的字符串，时间复杂度O(n),空间复杂度O(n),

/**
 * @param {string} str
 * @return {number}
 */
 function lengthOfLongestSubstring(str){
 if(!str || str.length < 0) return 0;
 let num = 0;
 let strArr = str.split('');
 let lengthOfSubstring = [];
 for(let i = 0; i < strArr.length; i ++){
 const index = lengthOfSubstring.indexOf(strArr[i])
 if( index <0 ){
 lengthOfSubstring.push(strArr[i])
 }else{
 lengthOfSubstring = lengthOfSubstring.splice(index+1) 
 lengthOfSubstring.push(strArr[i])
 }
 num = num<lengthOfSubstring.length?lengthOfSubstring.length:num
 }
 return num;
 }

方法二：双悬浮框从字符串首尾圈出满足条件的字符串，直到重合，时间复杂度O(n/2),空间复杂度O(n),

/**
 * @param {string} str
 * @return {number}
 */
function lengthOfLongestSubstring(str){
 if(!str || str.length < 0) return 0;
 let num = 0;
 let strArr = str.split('');
 let lengthOfStartSubstring = [];
 let lengthOfEndSubstring = [];
 let loopTime = strArr.length - 1
 for(let i = 0; i <= loopTime; i ++){
 const startIndex = lengthOfStartSubstring.indexOf(strArr[i])
 const endIndex = lengthOfEndSubstring.indexOf(strArr[loopTime-i])
 if( startIndex <0 ){
 lengthOfStartSubstring.push(strArr[i])
 }else{
 lengthOfStartSubstring = lengthOfStartSubstring.splice(startIndex+1)
 lengthOfStartSubstring.push(strArr[i])
 }
 if( endIndex <0 ){
 lengthOfEndSubstring.push(strArr[ loopTime-i])
 }else{
 lengthOfEndSubstring = lengthOfEndSubstring.splice(endIndex+1)
 lengthOfEndSubstring.push(strArr[loopTime-i])
 }
 console.log(lengthOfStartSubstring, lengthOfEndSubstring)
 let lengthOfSubstring = lengthOfStartSubstring.length>lengthOfEndSubstring.length?lengthOfStartSubstring.length:lengthOfEndSubstring.length
 num = num<lengthOfSubstring?lengthOfSubstring:num
 console.log(i)
 if(2*i - loopTime >= lengthOfStartSubstring.length) return;
 }
 return num;
}

[sisterAn]

解法一：维护数组

解题思路： 使用一个数组来维护滑动窗口

遍历字符串，判断字符是否在滑动窗口数组里

• 不在则 push 进数组
• 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
• 然后将 max 更新为当前最长子串的长度

遍历完，返回 max 即可

画图帮助理解一下：

代码实现：

var lengthOfLongestSubstring = function(s) {
 let arr = [], max = 0
 for(let i = 0; i < s.length; i++) {
 let index = arr.indexOf(s[i])
 if(index !== -1) {
 arr.splice(0, index+1);
 }
 arr.push(s.charAt(i))
 max = Math.max(arr.length, max) 
 }
 return max
};

时间复杂度：O(n²)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)

空间复杂度：O(n)

解法二：维护下标

解题思路： 使用下标来维护滑动窗口

代码实现：

var lengthOfLongestSubstring = function(s) {
 let index = 0, max = 0
 for(let i = 0, j = 0; j < s.length; j++) {
 index = s.substring(i, j).indexOf(s[j]) 
 if(index !== -1) { 
 i = i + index + 1 
 } 
 max = Math.max(max, j - i + 1) 
 }
 return max
};

时间复杂度：O(n²)

空间复杂度：O(n)

解法三：优化的Map

解题思路：

使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标

使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标

遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中

最后，返回 max 即可

代码实现：

var lengthOfLongestSubstring = function(s) {
 let map = new Map(), max = 0
 for(let i = 0, j = 0; j < s.length; j++) {
 if(map.has(s[j])) {
 i = Math.max(map.get(s[j]) + 1, i)
 }
 max = Math.max(max, j - i + 1)
 map.set(s[j], j)
 }
 return max
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

[zhaojinzhao]

function getMaxLen(str) {
var maxLen = 0, startIndex = 0;
for(var i = 0; i < str.length; i++) {
for(var j = startIndex; j < i; j++) {
if (str[j] === str[i]){
startIndex = j + 1;
break
}
}
maxLen = Math.max(maxLen, i - startIndex + 1);
}
return maxLen;
}

[fengmiaosen]

经典的滑动窗口算法题

var lengthOfLongestSubstring = function (s) {

 if (s.length < 2) {
 return s.length;
 }

 let window = new Map();

 let left = 0;
 let right = 0;

 let res = 0;

 while (right < s.length) {
 let rc = s[right];
 right++;

 if (window.has(rc)) {
 window.set(rc, window.get(rc) + 1);
 } else {
 window.set(rc, 1);
 }

 while (window.get(rc) > 1) {
 let lc = s[left];
 left++;

 if (window.has(lc)) {
 window.set(lc, window.get(lc) - 1);
 }
 }

 res = Math.max(res, right - left);
 }

 return res;
};

[lovetingyuan]

var lengthOfLongestSubstring = function(s) {
 let max = 0
 let map = {}
 let start = 0
 let end
 for (let i = 0; i < s.length; i++) {
 if (map[s[i]] >= 0) {
 start = map[s[i]] + 1
 }
 map[s[i]] = i
 end = i
 Object.keys(map).forEach(c => {
 if (map[c] < start) {
 map[c] = -1
 }
 })
 if (max < (end - start + 1)) {
 max = end - start + 1
 }
 }
 return max
};

[U-LAN]

代码中的 res 变量存储的是所有不重复子串及其长度，就本题目完全可以不需要这个变量，如果题目需要返回不重复子串则可以用到

var lengthOfLongestSubstring = function (str) {
 if (!str) return 0

 let res = {} // 存储所有不重复子串
 let max = 0 
 let s = ''

 for (const char of str) {
 let idx = s.indexOf(char)
 s += char

 if (idx === -1) { // 不重复

 res[s] = s.length // 存储不重复子串
 max = Math.max(max, s.length)

 } else { // 重复，从重复的字符的第一个个位置进行分割

 let del = s.slice(0, idx + 1)
 res[del] = del.length // 存储不重复子串
 max = Math.max(max, del.length)

 s = s.slice(idx + 1)
 res[s] = s.length // 存储不重复子串
 max = Math.max(max, s.length)
 }
 }
 res[s] = s.length
 max = Math.max(max, s.length)

 return max
}

[limeng01]

悬浮窗

var lengthOfLongestSubstring = function (s) {
 let next = 0;
	let start = 0;
	let arr = [];
	let len = 0;
	while (true) {
		if (arr.includes(s[next])) {
			arr = [];
			start++;
			next = start;
			if (start === s.length - 1) {
				return len;
				break;
			}
		} else {
			if (s[next]) {
				arr.push(s[next]);
				next++;
			} else {
				return len;
				break;
			}
		}
		len = arr.length > len ? arr.length : len;
	}
};

[JohnApache]

利用了 Map 存储已经存放的char

const lengthOfLongestSubstring = (source: string) => {
 if (source.length <= 1) return source.length;
 let i = 0;
 let map: Record<string, boolean> = {};
 let count = 0;
 let maxCount = 0;
 while (i < source.length) {
 const char = source.charAt(i);
 if (!map[char]) {
 count++;
 map[char] = true;
 i++;
 continue;
 }
 if (maxCount < count) {
 maxCount = count;
 }
 map = {}; count = 0;
 }
 return maxCount;
};