leetcode 3. 最长不含重复的子字符串的五种解法

超、凢脫俗 2022-10-19 08:18 95阅读 0赞

leetcode链接：[最长不含重复的子字符串][Link 1]

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

示例 1:

输入: s = "abcabcbb"
    输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。  
示例 2:

输入: s = "bbbbb"
    输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。  
示例 3:

输入: s = "pwwkew"
    输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。  
示例 4:

输入: s = ""
    输出: 0

提示：

0 <= s.length <= 5 \* 104  
s 由英文字母、数字、符号和空格组成

**方法一**

这道题可以用动态规划来解，思路解析：[https://zhuanlan.zhihu.com/p/80538556][https_zhuanlan.zhihu.com_p_80538556]

AC代码：

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.empty())   return 0;
            int cur_len = 0;
            int max_len = 0;
            int tmp = -1;
            std::map<char, int> lastindex;
            for(auto i = 0; i < s.length(); i++)
            {
                if(lastindex.find(s[i]) == lastindex.end()) // not found
                {
                    cur_len++;
    
                }
                else
                {
                    tmp = i - lastindex[s[i]];
                    if(tmp > cur_len)
                    {
                        cur_len++;
    
                    }
                    else
                    {
                        cur_len = tmp;
    
                    }
                }
                max_len = max(max_len, cur_len);
                lastindex[s[i]] = i;
            }
            return max_len;
        }
    };

**方法二**

思路解析：利用 hashset 来检查重复元素。

*  我们定义 l 和 r 两个指针表示一个特定的子字符串的首和尾。初始它们都在索引 0 处。
 *  移动 r，并同时向 hashset 中添加 r 所指的元素值，当 r 指到重复的元素时，r - l 的值就是一个不含重复字符的子字符串的长度。
 *  erase 掉 haseset 中的 l 所指元素的值，然后让 l++（for 循环的作用）。之后继续移动 r来找到下一个不含重复字符的子字符串的长度。

AC代码：

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.size()==0) return 0;
            unordered_set<char> store;
            int res=-1;
            int l=0,r=0;
            for(l=0;l<s.size();l++)
            {
                while(r<s.size()&&!store.count(s[r]))//set的count值只能是0或1
                {
                    store.insert(s[r]);
                    r++;
                }
                res=max(res,r-l);
                store.erase(s[l]);
                if(r>=s.size()) break;
            }
            return res;
        }
    };

但因为涉及到频繁的元素erase，这个耗时会比第一种方法略高。

**方法三**

思路解析：使用滑动窗口来做。  
窗口的范围为 `[left, right]，left，right`初始化为0。  
设置一个查找表 `lookup，lookup` 存储了当前窗口中的元素。`right` 先移动，如果 `s[right]` 不在 `lookup` 中，则 `right++`，`maxLen++`，将 `right` 加入 `lookup` 中；否则，将 `s[left]` 从 `lookup` 中移除（注意这里不是先移除重复的元素 `s[right]`，因为先移除 `s[right]` 的话就不满足连续子串这个要求了），将 `left++`，直至 `s[right]` 不在 `lookup` 中出现。当遇到了重复字符，我们一步一步地移动 left 指针。为了加快速度，我们可以直接将 `left` 移动到当前 `right` 的位置上。

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.empty()) return 0;
            vector<int> v(128, -1);
            int left = -1;
            int maxLen = 1;
            for(int right=0; right<s.size(); right++){
                char c = s[right];
                if(v[c]!=-1) left = max(left, v[c]);   // c 出现在了窗口中
                v[c] = right;
                maxLen = max(maxLen, right-left);
            }
            return maxLen;
        }
    };

**方法四**  
双指针，可以直接看代码和注释：

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if (!s.size()) return 0; // 判空
            int maxLength = 0; // 记录最长不包含重复字符的子字符串的长度
            int left = 0, right = 0; // 初始化双指针
            unordered_set<char> subStr; // 哈希表存储不包含重复字符的子串
            /*
            *  双指针遍历原字符串:
            *  外层左指针、内层右指针
            */
            while (left < s.size()) {
                /*
                *  右指针不断右移遍历字符串
                *  当遇到的字符在哈希表中不存在时，将其插入哈希表
                *  遇到哈希表中存在的字符 或 到原字符串结尾时跳出循环
                */
                while (right < s.size() && !subStr.count(s[right])) {
                    subStr.insert(s[right]);
                    right++;
                }
                /*
                *  更新最大子串的长度
                *  因为上面的循环跳出时right指向的是子串后面一个位置
                *  所以是right-left而不是right-left+1
                */
                maxLength = max(maxLength, right - left);
                /*
                *  若上面循环跳出是因为右指针到原字符串末尾，
                *  说明遍历完毕，最长不包含重复字符的子串已经找到
                *  直接跳出循环
                */
                if (right == s.size()) break;
                /*
                *  若上面循环跳出是因为遇到了哈希表中已有的字符
                *  则从左边开始挨个删除哈希表中的字符
                *  并且左指针右移
                */
                subStr.erase(s[left]);
                left++;
            }
            return maxLength;
        }
    };

**方法五**

背包

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            vector<int> vec(128);
            int res = 0, beg = 0, len = s.size();
            for(int i = 1; i <= len; ++i) {
                auto &x = vec[s[i-1]];
                if(beg < x) { beg = x; }
                if(res < i - beg) { res = i - beg; }
                x = i;
            }
            return res;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[https_zhuanlan.zhihu.com_p_80538556]: https://zhuanlan.zhihu.com/p/80538556