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

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

示例 1:

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

示例 2:

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

示例 3:

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

附leetcode：leetcode

对原数组进行判断，是否在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;
};

快慢指针维护一个滑动窗口，如果滑动窗口里面有快指针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

方法一：悬浮框圈出满足条件的字符串，时间复杂度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;
}

解法一：维护数组

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

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

不在则 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

经典的滑动窗口算法题

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;
};

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
};

代码中的 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
}

悬浮窗

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;
	}
};

利用了 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;
};

 let lengthOfLongestSubstring(str) {
      //对原数组进行判断，是否在arr里 如果在就将arr字符串之前的全部去除，不在就直接push，最后判断长度
      let arr = []
      let length = 0
      for (let m of str) {
        if (arr.includes(m)) {
          let index = arr.indexOf(m)
          arr.splice(0, index + 1);
        }
        arr.push(m);
        length = Math.max(arr.length, length)
      }

      return length
    }

function getMostNoRepeatChar(str){
    let obj = {}
    let maxLen = 0
    let curCount = 0
    for (let i=0;i<str.length;i++){
        if(obj.hasOwnProperty(str.charAt(i))){
            maxLen = curCount>maxLen?curCount:maxLen
            curCount = 0
            obj={}
            i--
        }else{
            obj[str.charAt(i)] = true
            curCount++
        }
    }
    return maxLen
}
console.log(getMostNoRepeatChar('abcabcbb'))
console.log(getMostNoRepeatChar('bbbbb'))
console.log(getMostNoRepeatChar('pwwkew'))

Navigation Menu

Repository navigation

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

解法一：维护数组

解法二：维护下标

解法三：优化的Map

悬浮窗

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

AiKunnnnn commented on Apr 21, 2020

Aiyoweioo commented on Apr 21, 2020

fanefanes commented on Apr 21, 2020

sisterAn commented on Apr 21, 2020

解法一：维护数组

解法二：维护下标

解法三：优化的Map

zhaojinzhao commented on May 7, 2020

fengmiaosen commented on Jun 16, 2020

lovetingyuan commented on Jul 5, 2020

U-LAN commented on Oct 21, 2020

limeng01 commented on Dec 7, 2020

悬浮窗

JohnApache commented on Apr 28, 2021

XW666 commented on Jun 30, 2021

AlexZhang11 commented on May 31, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions