探索LeetCode【0003】无重复字符的最长子串（未完成）
目录
- 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<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (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<char> 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时，需要注意以下几点：
- unordered_set中的元素必须是可哈希的，即需要定义哈希函数和相等比较函数。
- unordered_set中的元素是无序的，不能通过下标访问元素。
- unordered_set中的元素不允许重复，如果插入重复元素会被忽略。
下面是一个使用unordered_set的例子：
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
unordered_set<int> 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;
else
cout << "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<int> 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<int> m(128, 0); //ASCII码范围：0-127
int 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<int> m(128,0);//这个容器为了存当遇到相同的字符(假设是a)时i应该变成的值，即前面那个a的下一个字符
int ans=0; //最终的子串长度
int i=0;
for(int j=0;j<s.size();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码值，全部赋0
vector<int> 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++) {
//修改最左边的字母序号head
head = max(head, m[s[i]]);
//当前字母对应的ASCII码桶里存下一个位置(i+1)，用于更新head
m[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<char, int> hash;
while (end < sSize)
{
char tmpChar = s[end];
//仅当s[start,end) 中存在s[end]时更新start
if (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<int> vec(128, -1);
while (end < sSize)
{
char tmpChar = s[end];
//仅当s[start,end) 中存在s[end]时更新start
if (vec[int(tmpChar)] >= start)
{
start = vec[int(tmpChar)] + 1;
length = end - start;
}
vec[int(tmpChar)] = end;
end++;
length++;
result = max(result, length);
}
return result;
}
};