1. 题目来源
链接：
最长不含重复字符的子字符串
来源：LeetCode——《剑指-Offer》专项
2. 题目说明
给定一个字符串，请你找出其中不含有重复字符的
最长子串
的长度。
示例1：
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例2：
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例3：
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
-
s.length <= 40000
3. 题目解析
方法一：滑动窗口+HashMap+常规解法
这道题
字符出现的位置很重要
，所以可以使用
HashMap
来建立字符和其出现位置之间的映射。主要思路如下：
-
维护了一个滑动窗口，窗口内的都是没有重复的字符，需要尽可能的扩大窗口的大小
-
由于窗口在不停向右滑动，所以只关心每个字符最后出现的位置，并建立映射
-
窗口的右边界就是当前遍历到的字符的位置，
为了求出窗口的大小，需要一个变量 left 来指向滑动窗口的左边界
-
如果当前遍历到的字符从未出现过，那么直接扩大右边界
-
如果之前出现过，那么就分两种情况，在或不在滑动窗口内
- 如果不在，那么就没事，当前字符可以加进来
-
如果在，需要先在滑动窗口内去掉这个已经出现过的字符了，
去掉的方法并不需要将左边界
left
一位一位向右遍历查找，由于
HashMap
已经保存了该重复字符最后出现的位置，所以直接移动
left
指针就可以了。
-
维护一个结果
res
，每次用出现过的窗口大小来更新结果
res
，就可以得到最终结果啦。
注意将
left
初始化为 -1，在
i - left
时，不必判断单个字符的情况了。
参见代码如下：
// 执行用时 :40 ms, 在所有 C++ 提交中击败了28.37%的用户
// 内存消耗 :11.1 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
int res = 0, left = -1;
unordered_map<int, int> m;
for (int i = 0; i < s.size(); ++i) {
if (m.count(s[i]) and m[s[i]] > left) left = m[s[i]];
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
方法二：滑动窗口+vector映射数组+常规解法
下面这种写法是上面解法的精简模式，这里可以建立一个
256 位大小的整型数组来代替
HashMap
，这样做的原因是
ASCII
表共能表示 256 个字符，也是常见的哈希映射初始化方式，但是由于键盘只能表示 128 个字符，所以用 128 也行，然后全部初始化为 -1，
这样的好处是
:
不用像之前的
HashMap
一样要查找当前字符是否存在映射对了，对于每一个遍历到的字符，直接用其在数组中的值来更新
left
，
因为默认是 -1，而
left
初始化也是 -1，所以并不会产生错误，这样就省了 if 判断的步骤
，其余思路都一样。
参见代码如下：
// 执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :10.1 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(128, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
方法三：滑动窗口+HashSet+常规解法
下面这种解法使用了
HashSet
，核心算法和上面的很类似，把出现过的字符都放入
HashSet
中，遇到
HashSet
中没有的字符就加入
HashSet
中并更新结果
res
，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止。感觉这个的
滑动窗口
更加动感，更加形象。
// 执行用时 :32 ms, 在所有 C++ 提交中击败了41.72%的用户
// 内存消耗 :13.6 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = 0, i = 0, n = s.size();
unordered_set<char> t;
while (i < n) {
if (!t.count(s[i])) {
t.insert(s[i++]);
res = max(res, (int)t.size());
}
else {
t.erase(s[left++]);
}
}
return res;
}
};