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

题目要求

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

示例一

输入: s = “abcabcbb”

输出: 3

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

示例二

输入: s = “bbbbb”

输出: 1

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

示例三

输入: s = “pwwkew”

输出: 3

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

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

• 提示：

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

解题

滑动窗口

1. 最开始的时候

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

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

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

• • • 如果重复，移动START到重复字符的下一个位置
    • 如果不重复，则不移动

1. 1. 重新计算LENTH=END-START+1
   2. 对比当前LENTG和已记录的RESULT，取较大值为新RESULT

分析图中过程：

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

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

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

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

1. 右侧第二幅图中，END指向的新字符C与子串中字符C重复

1. 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_mapmp;  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. 1. 如vec[2]=3，意思是ASCII码中值为2的字符，目前最后一次出现在字符串中的第4个字符的位置

1. 判断END所指的字符在vector容器中存储的位置，是否大于START

• • 如果大于，则修改START，指向存储的位置的下一个位置
  • 否则，不操作START

代码

class Solution { public:  int lengthOfLongestSubstring(string s) {  int start(0), end(0), result(0);  vectorv(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网站查阅，边刷题边巩固

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=26uneso59lnoo