保亭黎族苗族自治县网站建设_网站建设公司_CSS_seo优化

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. \(right = 0,set.insert('p')\)
    2. \(right = 1,set.insert('w')\)
    3. \(right=2,'w'重复，ans=right-left = 2。此后我们调整left，直至删除上一次出现的'w'为止\)
    4. 删除后即为\(left=2,right=2\)，我们相当于又开始了一次新的字符串搜索，直至\(right\)遍历完整个字符串。
  • s = "djdv"
    1. \(right=0,set.insert('d')\)
    2. \(right=1,set.insert('j')\)
    3. \(right=2,'d'重复，ans = right - left = 2。此后我们调整left，直至删除上一次出现的'd'为止\)
    4. 删除后即为\(left=1,right=2\)，我们相当于是回到了\(right\)向右移动的一个中间步骤，直至\(right\)遍历完整个字符串。

复杂度

时间复杂度：\(O(n)\)
空间复杂度：\(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;}
};

# Python
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:temp = set()n = len(s)left, right, ans = 0, 0, 0while right < n:if s[right] not in temp:temp.add(s[right])right += 1ans = max(ans, right - left)else:temp.remove(s[left])left += 1return ans

// Rust
// use std::cmp;
use std::collections::HashSet;impl Solution {pub fn length_of_longest_substring(s: String) -> i32 {let mut temp = HashSet::new();let mut left = 0;let mut right = 0;let mut ans = 0;let n = s.len();// Rust无法直接通过索引访问字符，需要转化为Vec<char>let chars : Vec<char> = s.chars().collect();while right < 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;}}ans as i32}
}