目录

• 0、题目
• 1、官方答案（完全不懂）
• 2、第二个参考答案
• • 2.1 参考代码
  • 2.2 解释代码2中的`unordered_set`
• 3、第三个参考答案（需要进一步删减）
• 4、 第四个参考答案
• • 4.1 解法一，滑动窗口
  • 4.2 解法二，利用hashmap优化
  • 4.3 解法三，利用数组（桶代替hashmap）

0、题目

题目链接：【0003】无重复字符的最长子串

1、官方答案（完全不懂）

官方答案

代码1

class Solution {
public:int lengthOfLongestSubstring(string s) {// 哈希集合，记录每个字符是否出现过unordered_set occ;int n = s.size();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int rk = -1, ans = 0;// 枚举左指针的位置，初始值隐性地表示为 -1for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格，移除一个字符occ.erase(s[i - 1]);}while (rk + 1 < n && !occ.count(s[rk + 1])) {// 不断地移动右指针occ.insert(s[rk + 1]);++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = max(ans, rk - i + 1);}return ans;}
};

后续还有待进一步探索学习

2、第二个参考答案

2.1 参考代码

答案链接，并包含了其他与【滑动窗口】和【万能模板】相关的题目和答案

代码2

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0;unordered_set lookup;int maxStr = 0;int left = 0;for(int i = 0; i < s.size(); i++){while (lookup.find(s[i]) != lookup.end()){lookup.erase(s[left]);left ++;}maxStr = max(maxStr,i-left+1);lookup.insert(s[i]);}return maxStr;}
};

2.2 解释代码2中的unordered_set

上述代码2中，提到的unordered_set具体如下

unordered_set是C++ STL中的一个容器，用于存储一组不重复的元素，其内部实现是基于哈希表的。unordered_set中的元素是无序的，但是可以通过哈希函数快速查找元素。

unordered_set的用法和其他STL容器类似，可以使用insert()函数向其中插入元素，使用erase()函数删除元素，使用find()函数查找元素等。另外，unordered_set还提供了一些其他的成员函数，如size()、empty()、clear()等。

在使用unordered_set时，需要注意以下几点：

1. unordered_set中的元素必须是可哈希的，即需要定义哈希函数和相等比较函数。
2. unordered_set中的元素是无序的，不能通过下标访问元素。
3. unordered_set中的元素不允许重复，如果插入重复元素会被忽略。

下面是一个使用unordered_set的例子：

#include 
#include 
using namespace std;
int main()
{unordered_set mySet;mySet.insert(1);mySet.insert(2);mySet.insert(3);mySet.insert(2); //插入重复元素，会被忽略    cout << "mySet size: " << mySet.size() << endl; //输出元素个数    if (mySet.find(2) != mySet.end()) //查找元素2        cout << "2 is in mySet" << endl;elsecout << "2 is not in mySet" << endl;mySet.erase(3); //删除元素3    for (auto it = mySet.begin(); it != mySet.end(); ++it) //遍历元素        cout << *it << " ";cout << endl;mySet.clear(); //清空元素    cout << "mySet size: " << mySet.size() << endl; //输出元素个数    return 0;
}

输出情况为：

mySet size: 3
2 is in mySet
1 2
mySet size: 0

3、第三个参考答案（需要进一步删减）

链接

class Solution {
public:int lengthOfLongestSubstring(string s) {vector m(128, 0);int ans = 0;int i = 0;for (int j = 0; j < s.size(); j++) {i = max(i, m[s[j]]);m[s[j]] = j + 1;ans = max(ans, j - i + 1);}return ans;}
};

class Solution {
public:int lengthOfLongestSubstring(string s) {vector m(128, 0); //ASCII码范围：0-127int ans = 0;int i = 0;for (int j = 0; j < s.size(); j++) {if(m[s[j]]!=0)  i = max(i, m[s[j]]);m[s[j]] = j + 1;ans = max(ans, j - i + 1);}return ans;}
};

增加注释

class Solution {
public:int lengthOfLongestSubstring(string s) {vector m(128,0);//这个容器为了存当遇到相同的字符(假设是a)时i应该变成的值，即前面那个a的下一个字符int ans=0; //最终的子串长度int i=0;for(int j=0;j//如果遇到了相同的字符(假设为a)，此时m[s[j]]会又去到同样的存储单元m[a的ASCII码值]//因为之前遇到a时已经将这个位置的值改成前面那个a的下一个位置了，所以m[s[j]]大于i，将i更新i=max(i,m[s[j]]);m[s[j]]=j+1;//更新这个位置的值，当下次再遇到该字母时，将i调整到该字母下一个位置的地方ans=max(ans,j-i+1);//更新最终结果值，即没相同字母的子串的字符个数}return ans;}
};

改进注释：

class Solution {
public:int lengthOfLongestSubstring(string s) {//创建桶(数组)，设定128个元素对应0-127ASCII码值，全部赋0vector m(128, 0);//存最大长度int maxlen = 0;//head表示窗口最左边的字母序号：如果出现重复的，比如两个相同的字母a，上一个a在桶里存的m[s[i]]是a+1表示a的下一个位置//那么第二个a出现时，head就=a+1也就是max(head,m[s[i]])，去除了窗口里上一个a，保证窗口里无重复字母int head = 0;//遍历字符串for (int i = 0; i < s.size(); i++) {//修改最左边的字母序号headhead = max(head, m[s[i]]);//当前字母对应的ASCII码桶里存下一个位置(i+1)，用于更新headm[s[i]] = i + 1;//更新长度maxlen = max(maxlen, i - head + 1);}return maxlen;}
};

4、 第四个参考答案

4.1 解法一，滑动窗口

链接

class Solution
{
public:int lengthOfLongestSubstring(string s){//s[start,end) 前面包含 后面不包含int start(0), end(0), length(0), result(0);int sSize = int(s.size());while (end < sSize){char tmpChar = s[end];for (int index = start; index < end; index++){if (tmpChar == s[index]){start = index + 1;length = end - start;break;}}end++;length++;result = max(result, length);}return result;}
};

4.2 解法二，利用hashmap优化

链接

class Solution
{
public:int lengthOfLongestSubstring(string s){//s[start,end) 前面包含 后面不包含int start(0), end(0), length(0), result(0);int sSize = int(s.size());unordered_map hash;while (end < sSize){char tmpChar = s[end];//仅当s[start,end) 中存在s[end]时更新startif (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start){start = hash[tmpChar] + 1;length = end - start;}hash[tmpChar] = end;end++;length++;result = max(result, length);}return result;}
};

4.3 解法三，利用数组（桶代替hashmap）

链接

class Solution
{
public:int lengthOfLongestSubstring(string s){//s[start,end) 前面包含 后面不包含int start(0), end(0), length(0), result(0);int sSize = int(s.size());vector vec(128, -1);while (end < sSize){char tmpChar = s[end];//仅当s[start,end) 中存在s[end]时更新startif (vec[int(tmpChar)] >= start){start = vec[int(tmpChar)] + 1;length = end - start;}vec[int(tmpChar)] = end;end++;length++;result = max(result, length);}return result;}
};