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

中等题

如果是使用python，直接从最长的字符串开始递减遍历，然后判断子串是否无重复（字符串长度等于集合元素个数就行了），找到一个就结束遍历，会存在算法复杂度的问题。

假设字符串长度为n，外层循环n，将字符串转换为集合的 *** 作复杂度是O(n)，这样复杂度在O(n²)。

使用C++如果这么做也一样，只是没有那么方便判断无重复字符。

我想到的一个办法是，先内部排序（平均情况最好O(nlogn)），再遍历，如果相邻两个字符一样，就重复了，舍去。

这样做复杂度还要高于前面一种。

如果是小规模数据当然是没问题，如果数据很大那肯定是不行的。

装模做样分析一下，以上做法导致大量重复运算的地方在于对一个较长的字串判断是否重复后，其稍短一些的字串很有可能也包含了重复的字符，如aaaabbb和aaaabb（我减掉了最后一个字符）。

真正能够减少重复计算的方法只能是类似于KMP算法那样（只是类似），以滑动窗口的形式逐步逼近。

下面罗列一些思考的关键点：

• 新建左侧游标p，新建一个大于p的游标q（表示一直在p的右边），用pq来表示这个子串。
  

  
  

  这样做的好处是，p永远往右移动，q也永远往右移动，不用走回头路。
  

  
  

  一旦q的下一个字符使得子串重复，则记录这个子串长度，p往右移动1，否则q右移1直到结束。
  

  
  

• 子串，说明每一个位置的字符都有可能产生“最长无重复字串”，因此外循环需要对每个字符遍历。
  

  
  

  我一开始是这么想的，但后来发现可以和KMP一样直接跳。
  

  
  

  如“abcdefgc”，第一次循环检查到最大子串“abcdefg”，发现重复的是c，那直接定位到前一次重复c的下一个位置即d，然后检查“defgc”，就不用检查以b和c开头的了，因为他们肯定是不如以a开头的子串长的。
  

  
  

  这样的话每次放入集合的话，就要存储一下具体的位置。
  

  
  

  注意：存储的是“上一次该字符出现”的位置。
  

  
  

  如果写代码逻辑的话，应该是“如果是第一次出现，记录位置；如果已经存在，更新为现在这个位置”。
  

  
  

  不过在C++中用什么数据结构来存储呢？答案是map（补课），python可以用字典。
  

  
  

• 关于判断是否有重复字符的 *** 作，C++里也有集合，这个我还真没用过（补课）。
  

  
  

  C++标准模板库里提供了几种集合，常用的有set头文件里的std::set和unordered_set头文件里的std::unordered_set，前者有序，后者无序。
  

  
  

形象地说，就是一前一后两个游标夹着中间的子串往右移动，然后记录最长的就可以了。

代码如下：

    int lengthOfLongestSubstring(string s) {
        int len = s.size(); //字符串长度
        int maxlen = -1; //最长
        int p = 0, q = 0; //左右游标
        set<char> st = {}; //字符集
        unordered_map<char, int> mp; //暂存位置
        while (p < len && q < len) {
            //如果不在集合，加入集合，并标记位置
            if (st.find(s[q]) == st.end()) {
                st.insert(s[q]);
                mp.insert(pair<char, int>(s[q], q));
                q++;
            }
            else if (q == len) {
                p++;
                q = p;
                break;
            }
            else {
                //出现重复，先记录大小，再跳
                int size = st.size();
                maxlen = max(maxlen, size);
                //查找mp，找到重复的这个s[q]的上一次出现，还得删掉跳到这个之后的，以及集合中的
                pair<char, int> pir = *mp.find(s[q]);
                p = ++pir.second;
                for (unordered_map<char, int> ::iterator it = mp.begin(); it != mp.end(); ) {
                    if (it->first == s[q]) {
                        break;
                    }
                    st.erase(it->first);
                    it = mp.erase(it);
                }
                mp.erase(mp.begin());
                mp.insert(pair<char, int>(s[q], q));
                st.insert(s[q]);
                q++;
            }
        }

        return maxlen;
    }

我是这么想的，但是提交oj却报错，错的也很奇怪。

对于字符串’pwwkew’，我在本地运行结果明明是3，到了他那他偏说我是4。

我也懒得去找问题在哪里了，我没plus会员不能单步分析，反正这个代码也得继续优化。

我自认为这么做应该是没问题的，虽然很笨，但就当复习C++容器用法。

我用有序集合st存匹配到的单词，用无序map存子串的位置。

没有子串重复字符就往两个容器里加，遇到重复就左指针右移到重复字符的下一位，删除其经过的所有单词，再把右指针所指字符加入两个容器，直到到头。

先复习一下C++容器的用法。

有序集和无序集，区别在于有序集是基于二叉排序树的，插入即排序。

无序集插入并不排序。

这里用哪个都无所谓。

有序map和无序map，同理，但是这里需要无序map，因为我每次遇到重复更新会先进来的，本质上就是队列进出。

C++容器的元素访问多用iterator迭代器比较好，又能访问，又是指针，也不大。

循环删除的话注意循环内部的语句it = mp.erase(it)；不仅将it所指向的pair删除了，还向后移动了一个。

pair类似于Python的键值对元组，不过只能有两个元素，本身是一个struct。

访问方法是pir.first和pir.second。

上述做法显得臃肿，原因就在于我用了两个数据结构来分别存储位置和字符，但是事实上我根本不需要知道哪个字符在哪里这种细节，我只要知道1.当前子串里有哪些字符2.按队列进出顺序更新当前子串。

综合考虑，这样只需要用一个无序集合就可以完全做到了。

代码如下：

int lengthOfLongestSubstring(string s) {
        unordered_set<char>u; //无序集合，存储子串
        int left=0,right=0,Max=0; //左右指针，最大值
        int n=s.size(); //长度
        while(right<n){ 
            if(u.end()==u.find(s[right])){ //没有重复
                u.insert(s[right++]); //右指针右移，一直添加
                Max=max(right-left,Max); //更新最大值
            } else u.erase(s[left++]); //重复就从无序集合左侧不断移除，直到删掉了某个后，没有重复了，会继续添加
        }
        return Max;
    }

通过以上的思考，可见数据结构对于算法的重要性。

还有s[right++]这样的写法要熟悉。

做完这道题我应该掌握：

• 滑动窗口解题的大概思路：两个指针不回退地运动。
  

  
  

• C++ STL容器类的选择：有序还是无序。
  

  
  

• C++ pair + map替代Python字典。
  

  
  

• while循环的好处：非常自由，自由规定何时循环变量++。
  

  
  

• C++容器类find：u.find(iterator) == u.end()即寻找失败，成功会返回找到的迭代器。