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

发表于： 分类于：
字数： 638 阅读：≈ 2分钟

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

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

思路

基本思想

子串是连续的子串，也就是说不能删除元素，如果可以删除元素的话，直接使用回溯法遍历得到幂集，然后找幂集中最长的不重复子串即可

这里需要找到最长的不重复连续子串，可以考虑使用滑动窗口，因为这里求的是一个连续的序列，当滑动窗口中出现了重复的元素，就从左边开始删除，直到删除到滑动窗口中没有重复的元素为止，为了尽可能快的找到滑动窗口中是否存在当前元素，也就是出现了重复，可以使用unordered_set来记录当前滑动窗口中有哪些元素

从左边删除是因为需要连续的子串，左边的元素已经遍历过了

核心的思想就是滑动窗口中保留的用元素不重复的子串，这样每新来一个元素，就可以判断新的滑动窗口中的子串是不是最长的

执行流程

  1. 遍历字符串
  2. 滑动窗口中出现与当前的元素相同的重复元素，就将左边的元素删除，直到没有重复的元素出现
  3. 将当前的元素加入滑动窗口，保持滑动窗口的连续性
  4. 每次都判断是不是最长的连续子序列
  5. 返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    //滑动窗口直接解决问题
    int lengthOfLongestSubstring(string s) {
        //unordered_set当成一个滑动窗口
        unordered_set<char> uset;
        int left=0;
        int res=0;
        for(int i=0;i<s.size();++i){
            //当前元素在当前窗口中重复出现，需要删除到没有重复元素为止
            //删除的是最左边的元素
            while(uset.find(s[i])!=uset.end()){
                //从左边删除元素
                uset.erase(s[left]);
                left++;
            }
            //到这里滑动窗口中没有重复元素,将当前的新元素加入
            uset.insert(s[i]);
            res=res>uset.size()?res:uset.size();
        }
        return res;
    }
};

总结

核心就在保持滑动窗口的性质，从左边删除