LeetCode、3无重复最长子序列

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

难度中等7743收藏分享切换为英文接收动态反馈

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

示例 1:

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

示例 2:

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

示例 3:

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

本题使用的做法是滑动窗口，用C++中的set来维持

题目的大意应该是，提供一个字符串，要找到其中不重复的最长字串

大概思路应该是这样的，提供一个窗口，不断的向后插入字符串中的元素，一旦插入的元素重复，就将窗口的起始位置向前移动一位，不断记录窗口的大小，找到其中的最大值

这里的滑动窗口我用画图来进行解释

这里举个例子  acdfcf ， 很容易看出，最长的子串应（之一）该为acdf ， 长度为4

现在将a放入窗口

 

此时字串的最大长度为1，即maxsize = 1

 因为c在窗口中没有重复，所以将c也插入窗口中

 此时maxsize = 2 ，d在窗口中没有出现过,所以将d放入窗口中

 此时maxsize = 3  ，f不在窗口中重复，将f插入窗口

 家人们，关键点来了，c在窗口中出现过，因此，我们要移动窗口的左侧，直到窗口不再出现重复为止

 

将a移除窗口，可是如果将c插入，还是重复，所以我们继续将窗口左侧缩小 

 

 

此时size = 3 ， maxsize = 4，maxsize不进行更新

 现在插入f

 窗口中有重复元素，所以开始从左缩小窗口

 

 此时size = 2  ， maxsize  = 4 ， 最后算出来，最长不重复子串应该是4

了解了大概的思路，现在就开始coding吧

首先我们需要对空字符串进行特判，如果字符串为空，则直接返回

  if(s==""){
            return 0;
        }

进行一些初始化

        int left =0,right =0;
        int maxsize =0;
        set<char> detect;

现在我们进行对字符串的插入，当插入的字符没有在滑动窗口中出现过的时候，就直接进行插入，并且更新maxsize

      if(detect.find(s[right])==detect.end()){
                detect.insert(s[right]);
                if(detect.size()>maxsize){
                    maxsize = detect.size();
                }
            }

这里使用了set容器中的find ，用来寻找容器中是否有相同的元素，没有的话就返回end（末端）

，有的话就返回相同元素所在位置。

当找到相同元素的时候，我们现在应该移动滑动窗口的左侧，直到没有重复为止

        for(right =0;right<s.size();right++){
            while(detect.find(s[right])!= detect.end()){
                detect.erase(s[left]);
                left++;
            }

最后将完整代码放上 ， 希望能帮助到大家

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s==""){
            return 0;
        }
        int left =0,right =0;
        int maxsize =0;
        set<char> detect;
        for(right =0;right<s.size();right++){
            while(detect.find(s[right])!= detect.end()){
                detect.erase(s[left]);
                left++;
            }
            if(detect.find(s[right])==detect.end()){
                detect.insert(s[right]);
                if(detect.size()>maxsize){
                    maxsize = detect.size();
                }
            }
        }
        return maxsize;
    }
};