【基础篇 - Day 22】 2023-03-06 - 3. 无重复字符的最长子串 （04. 哈希表）

[threedayAAAAA]

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

 

示例 1:

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

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

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

提示：

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

双指针 + set

代码

function lengthOfLongestSubstring(s: string): number {
    let res = 0
    const charSet = new Set<string>()
    for(let start = 0, end = 0; start < s.length; start++){
        while(end < s.length && !charSet.has(s[end])){
            charSet.add(s[end])
            end++
        }
        res = Math.max(res, end - start)
        charSet.delete(s[start])
    }
    return res
};

时空复杂度

• 时间复杂度： O(N)
• 空间复杂度: O(N)

[MiumMi]

思路

双指针遍历即可实现

代码

function lengthOfLongestSubstring(s: string): number {
    const size = s.length;
    let result = 0;
    let endIndex = 0;
    const stringSet = new Set();
    for(let i = 0; i < size; i++) {
        if (i !== 0) {
            stringSet.delete(s[i - 1]);
        }
        while(endIndex < size && !stringSet.has(s[endIndex])) {
            stringSet.add(s[endIndex]);
            endIndex++;
        }
        result = Math.max(result, endIndex - i);
    }
    return result;
};

---

分析

时间复杂度： O(n) 空间复杂度： O(n)

[yunliuyan]

思路

• 哈希表，将字符串的值长度存到哈希表中
• 若已经存在哈希表中，记录哈希表的长度，哈希表清除相同字符之前的字符串，存当前字符
• 若再次遇到存在的哈希值，则和上次的长度比大小，留最大值

  代码

  function lengthOfLongestSubstring(s: string): number {
  let res = 0;
  const hashMap: Map<string, number> = new Map();
  for (let i = 0; i < s.length; i++) {
      if (hashMap.has(s[i])) {
          res = Math.max(res, hashMap.size);
          let repeatValue = hashMap.get(s[i]);
          hashMap.forEach((value, index) => {
              if (value <= repeatValue) {
                  hashMap.delete(index);
              }
          })
      }
      hashMap.set(s[i], i);
  }
  return Math.max(res, hashMap.size);
  };

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)