题目要求

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

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

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

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

提示：
- 0 <= s.length <= 54
- s 由英文字母、数字、符号和空格组成

原题链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

解题

滑动窗口

力扣3-无重复字符的最长子串

最开始的时候
1. 创建START、END指向字符串最前端的位置
2. 创建LENTH记录当前长度
3. 创建RESULT记录无重复字符的最长字串长度
使用循环，向后移动END
1. 检查END指向的新字符是否与字串内的字符重复
  - 如果重复，移动START到重复字符的下一个位置
  - 如果不重复，则不移动
2. 重新计算LENTH=END-START+1
3. 对比当前LENTG和已记录的RESULT，取较大值为新RESULT

分析图中过程：

上图中，左侧三步中均无重复字符
1. START停留在原地不动，END++
右侧第一幅图中，END指向的新字符A与子串中字符A重复
1. START移动到原子串中字符A的下一个位置，即字符B所在位置
2. LENTH=3；
3. RESULT=3；
右侧第二幅图中，END指向的新字符C与子串中字符C重复
1. START移动到原子串中字符C的下一个位置，即字符A所在位置
2. LENTH=2
3. RESULT=3

敲代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        for (int index = 0; index < s.size(); index++)
        {
            end = index;
            for (int i = start; i < end; i++)
            {
                if (s[i] == s[end])
                {
                    start = i + 1;
                    //及时跳出
                    break;
                }
            }
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果执行用时: 8 ms 内存消耗: 6.7 MB

哈希表

思路与滑动窗口相同，不同的是查找重复元素的方式

滑动窗口是用遍历字符串的方式
哈希表是用容器自带的find方法

需要注意的是：

查找到重复元素后，要将表中记录的该元素的位置修改为最新位置
由于重新确定区间后，不清楚到底少了哪些元素，所以判断重复元素时，应确保该位置在START之后

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        unordered_map<char, int>mp;
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (mp.find(s[i]) != mp.end() && mp[s[i]] >= start)
            {
                start = mp[s[i]] + 1;
            }
            mp[s[i]] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果执行用时: 20 ms 内存消耗: 8.1 MB

桶优化

判断是否出现过时，利用vector容器代替哈希表以优化时间

int[26]用于字母'a'-'z'或'A'-'Z'
int[128]用于ASCII码
int[256]用于扩展ASCII码

思路与前两种方法相同，不同的仍是检验重复的方法

每次移动END，都将END指向的字符转化为ASCII码对应的数字
vector容器中对应的数字下标的值存储的是改数字最后出现的位置
1. 如vec[2]=3，意思是ASCII码中值为2的字符，目前最后一次出现在字符串中的第4个字符的位置
判断END所指的字符在vector容器中存储的位置，是否大于START
- 如果大于，则修改START，指向存储的位置的下一个位置
- 否则，不操作START

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        vector<int>v(128, -1);
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (v[int(s[i])] >= start)
            {
                start = v[int(s[i])] + 1;
            }
            v[int(s[i])] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果执行用时：8 ms, 在所有 C++ 提交中击败了88.74%的用户内存消耗：7.4 MB, 在所有 C++ 提交中击败了79.74%的用户

总结

力扣给这道题的分类是中等，对新手来说很难，而且还用到了两个指针，虽然上面的代码中用的是下标访问的方式，不是严格的指针，但也不容易，建议就是多看看题解，多写几遍代码，对于容器和重载的一些方法，可以随时去cplusplus网站查阅，边刷题边巩固

秒客网

力扣3-无重复字符的最长子串

题目要求

解题

滑动窗口

哈希表

桶优化

总结

相关文章