LeetCode 3.无重复字符的最长子串

3.无重复字符的最长子串

题面：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
【字串】：子字符串 是字符串中连续的 非空 字符序列。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。
示例 2:

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

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

解析：

• 针对于本道题目而言，Hot题单中放在了滑动窗口的位置，滑动窗口一般是处理连续序列时采用的方法，针对于一个大的字符串or列表而言，滑动窗口相当于是在大的列表中利用left与right两个指针开辟了一个小的连续列表，正是因为如此，其对于连续的子序列or字串问题是一个很不错的方法，两个指针指定的范围其间就是连续的，我们可以保证答案满足连续的要求。
• 话题转移到这道题目上来就是，我们要找的就是一个长字符串中的一个小字符串，该字符串需满足无重复的字符元素且长度最长。对于滑动窗口而言，我们利用这个窗口的右边界不断地向右探索，每次探索到新的字符时，在哈希表中检测目前的s[left:right]中是否已经存在该字符了，如若不存在，那就在哈希表中加入；反之，我们需要更新ans，此后将left向右移动，同时删除前面的哈希表中的字符，因为其已经被中断了，直至s[right]不在现有的哈希表中。
• 例如：
  • s = “pwwkew”：
    1. r i g h t = 0 , s e t . i n s e r t ( ′ p ′ ) right = 0,set.insert('p')right=0,set.insert(′p′)
    2. r i g h t = 1 , s e t . i n s e r t ( ′ w ′ ) right = 1,set.insert('w')right=1,set.insert(′w′)
    3. r i g h t = 2 , ′ w ′ 重复， a n s = r i g h t − l e f t = 2 。此后我们调整 l e f t ，直至删除上一次出现 的 ′ w ′ 为止 right=2,'w'重复，ans=right-left = 2。此后我们调整left，直至删除上一次出现的'w'为止right=2,′w′重复，ans=right−left=2。此后我们调整left，直至删除上一次出现的′w′为止
    4. 删除后即为l e f t = 2 , r i g h t = 2 left=2,right=2left=2,right=2，我们相当于又开始了一次新的字符串搜索，直至r i g h t rightright遍历完整个字符串。
  • s = “djdv”
    1. r i g h t = 0 , s e t . i n s e r t ( ′ d ′ ) right=0,set.insert('d')right=0,set.insert(′d′)
    2. r i g h t = 1 , s e t . i n s e r t ( ′ j ′ ) right=1,set.insert('j')right=1,set.insert(′j′)
    3. r i g h t = 2 , ′ d ′ 重复， a n s = r i g h t − l e f t = 2 。此后我们调整 l e f t ，直至删除上一次出现 的 ′ d ′ 为止 right=2,'d'重复，ans = right - left = 2。此后我们调整left，直至删除上一次出现的'd'为止right=2,′d′重复，ans=right−left=2。此后我们调整left，直至删除上一次出现的′d′为止
    4. 删除后即为l e f t = 1 , r i g h t = 2 left=1,right=2left=1,right=2，我们相当于是回到了r i g h t rightright向右移动的一个中间步骤，直至r i g h t rightright遍历完整个字符串。

复杂度

时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( m i n ( n , m ) ) （ m 为字符集大小） O(min(n, m))\ （m为字符集大小）O(min(n,m))（m为字符集大小）

Code

// C++ class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char> temp; int left = 0; int right = 0; int ans = 0; int n = s.size(); while (right < n) { auto it = temp.find(s[right]); if (it == temp.end()) // 当前set中不存在该字符记录 { temp.insert(s[right]); right++; ans = max(ans, right - left); } else { temp.erase(s[left]); left++; } } return ans; } };

# PythonclassSolution:deflengthOfLongestSubstring(self,s:str)->int:temp=set()n=len(s)left,right,ans=0,0,0whileright<n:ifs[right]notintemp:temp.add(s[right])right+=1ans=max(ans,right-left)else:temp.remove(s[left])left+=1returnans

// Rust// use std::cmp;usestd::collections::HashSet;implSolution{pubfnlength_of_longest_substring(s:String)->i32{letmuttemp=HashSet::new();letmutleft=0;letmutright=0;letmutans=0;letn=s.len();// Rust无法直接通过索引访问字符，需要转化为Vec<char>letchars:Vec<char>=s.chars().collect();whileright<n{if!temp.contains(&chars[right]){temp.insert(chars[right]);right+=1;// ans = cmp::max(ans, right - left);ans=ans.max(right-left);}else{temp.remove(&chars[left]);left+=1;}}ansasi32}}