【leetcode】第3题无重复字符的最长子串(Longest Substring Without Repeating Characters)做题记录 C++实现

朴灿烈づ我的快乐病毒、 2022-02-24 12:12 132阅读 0赞

leetcode第3题  
\#3. 无重复字符的最长子串(Longest Substring Without Repeating Characters)

今天把第三题做完了，各个方法都尝试了一下，思考与学习的时间有点长，说难也不难，其中有一些坑，趁还记着记录一下。

## **题目描述** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70]

题目里没有限定字符取值范围，根据做题结果来看，测试集数据中的字符范围是128个ASCII码，没有用到扩展ASCII码。

## **关于解法** ##

暴力破解法不说了，一般都能想到。

**滑动窗口法**需要思考一下才能想出来，解法思路如下：  
求字符串 str 中无重复字符的最长子串的长度  
设 set 为存储当前子串的集合  
设两个索引 i 和 j，i 代表当前子串起点，j 代表当前子串终点；

1.  初始状态 i = 0, j = 0，开始遍历 str；
2.  检查字符 str\[j\] 是否已经在集合 set 中，若不在，将其添加到 set 之中；若在，说明字符重复，当前以 str\[i\] 开头的字符串已经达到最大长度，计算当前长度并与之前的长度比较取最大值，随后从集合 set 中删除 str\[i\]，i++，即 i 往右移一位;
3.  如此循环，直到 i 遍历完 str 的所有字符，此时以每个 str\[i\] 为起始的最长子串都计算结束，其中长度最大的即为题目所求。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
    因为 i 和 j 都需要遍历一次 str，所以时间复杂度为 O(2\*n)，n 为 str 的长度

重点说一下**优化版滑动窗口**解法：  
大体思路和滑动窗口类似，但是在 i 的变化上有些改变，仔细想想大家应该能想到，当 str\[j\] 与子串 str\[i\]…str\[j-1\] 中的某个字符重复时，若该重复字符位于子串中间，滑动窗口需要重复判断若干次才能让 i++ 的值超过该重复字符的索引值，如下图所示，当 j 指向第二个 c 的时候，i 需要再重复判断字符 ‘c’ 是否已经在子串 str\[i\]…str\[j-1\] 中，一共重复判断了 4 次，i 才能够到达 d 所在的位置，所以这中间就浪费了很多时间。  
![在这里插入图片描述][20190404002312459.]  
所以，**优化的思路**就是直接跳过重复判断的部分，让 i 直接指向第一个 ‘c’ 的下一位置，即 ‘d’。  
因此我们需要一个类似索引数组的容器，如 map 或者 hashmap，遍历时存储下当前字符在 str 中索引（下标）的下一位，以便当再次遇到此字符时，我们直接让 i 指向存储好的索引，从而跳过了重复判断的阶段。比如上图，如果我们存储下第一个 ‘c’ 的下一个下标 4，当 j 指向 第二个 ‘c’ 时，我们直接让 i = 4，此时 i 就能直接指向 ‘d’ 了，减少了很多重复比较的时间。

以下是我的代码：

// 方法1，暴力法，略
    
        // 方法2，滑动窗口1
        // 使用一个set存储当前子串，判断当前的s[j]是否存在set中，若存在，表示有重复元素，当前以s[i]开头的子串已达到最大长度，
        // 此时将set中的set[i]删除，i++，即右移一位
        int lengthOfLongestSubstring2(string s) {
        
            set<char> substr_set;
            int s_len = s.length();
            int i = 0, res = 0, j = 0;
            while(i < s_len && j < s_len) {
        
                if(substr_set.find(s[j]) == substr_set.end()) {
             // 如果set中没有包含s[j]，将其插入set中
                    substr_set.insert(s[j++]);
                    res = max(res, j - i);
                } else {
                                                    //  如果s[j]已存在set中，删除s[i]，i++
                    substr_set.erase(s[i++]);
                }
            }
    
            return res;
        }
    
        // 方法3，滑动窗口2
        // 使用一个map存储当前子串，以及子串中每一个字符在s中的索引（下标）的下一位
        // 当s[j]存在于map中时，当前以s[i]开头的子串已达最大长度，
        // i 直接跳到map中与s[j]一样的字符的下标的下一位
        int lengthOfLongestSubstring3(string s) {
        
            map<char, int> substr_map;                                  // 记录子串字符以及字符的索引（下标）的下一位
            int s_len = s.length();
            int i = 0, res = 0, j = 0;
            for( ; j < s_len; j++) {
        
                map<char, int>::iterator iter = substr_map.find(s[j]);  // 查找字符 s[j] 是否已在子串中，即map中
                if( iter != substr_map.end()) {
                                 // 若在，表示字符重复
                    i = max(iter->second, i);                           // 重复字符下一个位置和当前i比较，防止 i 往回跳
                    substr_map[s[j]] = j + 1;   	                    // 更新重复字符s[j]的位置索引，取靠后的位置。 这两行实现了不需要删除map中跳过的字符
                }else{
        
                    substr_map.insert( pair<char, int>(s[j], j + 1 ) ); // 若不重复，插入s[j]及其索引的下一位
                }
                res = max(res, j - i + 1);                              // 更新最长无重复子串的长度
            }
            return res;
        }
    
        // 方法4，字符集
        // 思路和优化版滑动窗口类似  ，使用数组 index 存储所有字符在 s 中的索引的下一位置
        // 刚开始 index[s[j]] 都为0， i 也一直为0， 当出现重复元素时， i 直接跳到重复元素当前存在index数组中的下标位置。
        int lengthOfLongestSubstring4(string s) {
        
            int s_len = s.length();
            int index[128] = {
        0};
            int i = 0, res = 0, j = 0;
            for( ; j < s_len; j++) {
                    // 遍历 s 字符串
                i   = max(index[s[j]], i);      // 更新 i ，当没遇到重复元素时，i 一直保持不变。
                res = max(res, j - i + 1);
                index[s[j]] = j + 1;
            }
            return res;
        }

其中方法4的效率最高，

所掉进的坑：

1.  本以为仿照以前写C语言时用 “字符-‘0’ ”的方式就能作为数组索引了，后来经过测试和仔细看了一下ASCII码表，发现原来直接s\[j\]就能作为索引，而且 “字符-‘0’ ”只是48号以后的字符，包括的不全，所以就出现了下面的报错。  
    ![在这里插入图片描述][2019040400350128.]
2.  java的map.put()方法能更新map中的值，而C++的map.insert()方法不能更新值，只能添加map中没有的键值，所以得添加`substr[s[j]] = j+1;` 用于更新字符的位置。当时卡在着挺久才找到原因，对C++还不够熟悉。
3.  同时，在方法 3 的实现过程中，看到官方的题解我还产生了一个疑问：为什么添加子串字符的时候，添加的不是当前字符的位置，而是当前字符的下一个位置。  
    后来在实现方法 4 的时候我才明白，是因为若添加的是当前字符的位置，那在方法 3 中更新 i 的值以及更新最大长度值的时候，会产生错误，j - i 有可能会小于 0，最后导致最大长度计算错误（如输入的字符串是“ ”，长度为 1 时）。  
    要避免这个错误还得加上一些判断语句，想必作者是为了简便才如此设计的。

以上。  
如有错误欢迎指正哈！?

[github地址][github]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70]: /images/20220224/43b0aff89e3b4bf7acebca9030bfe017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220224/5d7412fde87f4715a457da464dca20c9.png
[20190404002312459.]: /images/20220224/f03ff03b215c46eb958ccfadbc3a9b9f.png
[2019040400350128.]: /images/20220224/bf7e1ba0293d43778f55bee3425d5fb0.png
[github]: https://github.com/yohstone/Programming-practice/blob/master/leetcode-3-longest%20substring.cpp