🥈Medium

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

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

示例 2:

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

示例 3:

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

题解

思路清晰的话，做起来还是比较简单的。遍历整个字符串，遍历的同时需要把遍历过的字符存储到数组（哈希表）temp中，遍历下一个字符的同时搜索该字符是否在temp中存在，如果存在，就需要把该字符第一次出现的位置之前字符清空，接着遍历

Python

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         if not s:
  4.             return 0
  5.         temp=[]
  6.         maxlength=0
  7.         length = 0
  8.         for i in s:
  9.             if i not in temp:
  10.                 temp.append(i)
  11.             else:
  12.                 begin = temp.index(i)
  13.                 length = len(temp)
  14.                 if (length>maxlength):
  15.                     maxlength = length
  16.                 temp = temp[begin+1:]
  17.                 temp.append(i)
  18.                 length = 0
  19.         if (len(temp)>maxlength):
  20.             maxlength = len(temp)
  21.         return maxlength

上面用了数组来存储之前的字符，搜索的时间会是🥈3. 无重复字符的最长子串 - 图1，所以需要改成哈希表，需要用set

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         # 哈希集合，记录每个字符是否出现过
  4.         occ = set()
  5.         n = len(s)
  6.         # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  7.         rk, ans = -1, 0
  8.         for i in range(n):
  9.             if i != 0:
  10.                 # 左指针向右移动一格，移除一个字符
  11.                 occ.remove(s[i - 1])
  12.             while rk + 1 < n and s[rk + 1] not in occ:
  13.                 # 不断地移动右指针
  14.                 occ.add(s[rk + 1])
  15.                 rk += 1
  16.             # 第 i 到 rk 个字符是一个极长的无重复字符子串
  17.             ans = max(ans, rk - i + 1)
  18.         return ans

JavaScript

  1. var lengthOfLongestSubstring = function(s) {
  2.     // 哈希集合，记录每个字符是否出现过
  3.     const occ = new Set();
  4.     const n = s.length;
  5.     // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  6.     let rk = -1, ans = 0;
  7.     for (let i = 0; i < n; ++i) {
  8.         if (i != 0) {
  9.             // 左指针向右移动一格，移除一个字符
  10.             occ.delete(s.charAt(i - 1));
  11.         }
  12.         while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
  13.             // 不断地移动右指针
  14.             occ.add(s.charAt(rk + 1));
  15.             ++rk;
  16.         }
  17.         // 第 i 到 rk 个字符是一个极长的无重复字符子串
  18.         ans = Math.max(ans, rk - i + 1);
  19.     }
  20.     return ans;
  21. };