题目要求

给定一个字符串 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/

解题

滑动窗口

1. 最开始的时候

   1. 创建START、END指向字符串最前端的位置
   2. 创建LENTH记录当前长度
   3. 创建RESULT记录无重复字符的最长字串长度

2. 使用循环，向后移动END

   1. 检查END指向的新字符是否与字串内的字符重复

      • 如果重复，移动START到重复字符的下一个位置
      • 如果不重复，则不移动
   2. 重新计算LENTH=END-START+1
   3. 对比当前LENTG和已记录的RESULT，取较大值为新RESULT

分析图中过程：

1. 上图中，左侧三步中均无重复字符

   1. START停留在原地不动，END++

2. 右侧第一幅图中，END指向的新字符A与子串中字符A重复

   1. START移动到原子串中字符A的下一个位置，即字符B所在位置
   2. LENTH=3；
   3. RESULT=3；

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方法

需要注意的是：

1. 查找到重复元素后，要将表中记录的该元素的位置修改为最新位置
2. 由于重新确定区间后，不清楚到底少了哪些元素，所以判断重复元素时，应确保该位置在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码

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

1. 每次移动END，都将END指向的字符转化为ASCII码对应的数字

2. vector容器中对应的数字下标的值存储的是改数字最后出现的位置

   1. 如vec[2]=3，意思是ASCII码中值为2的字符，目前最后一次出现在字符串中的第4个字符的位置

3. 判断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网站查阅，边刷题边巩固