LeetCode Medium｜【3. 无重复字符的最长子串】
力扣题目链接
状态：在本题中，我们可以很明显得看出出现了关键字：子串、最长，所以我们肯定是选用滑动窗口来解决这个题目。
滑动窗口首先要解决的就是我们选择什么样的容器来存储数据呢？本体中是计算重复字符，我们可以使用 set、map、数组均可以解决，这里分别给出三种方法。
set
这个非常直观，和我们做的一些滑动窗口的基础题是一样的
class Solution {
public:int lengthOfLongestSubstring(string s) {std::unordered_set<char> set;int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];while (set.find(rChar) != set.end()) {set.erase(s[left]);left++;}set.insert(rChar);ans = max(ans, right - left + 1);right++;}return ans;}
};
map
对于 map ，我们最需要搞清楚的就是 key 和 value ，这里我们的 key 肯定是字符，然后 value 肯定是对应的下标，因为我们的 map 只能去搜索 key。
这样的话我们就不需要内层循环了，可以直接更新 left 。如何更新呢？当然就是把重复字符排除在外，但是为了防止 left 的回退，所以我们有：
left = max(left, map[rChar] + 1);
这样的代码。
class Solution {
public:int lengthOfLongestSubstring(string s) {std::unordered_map<char, int> map;int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];if (map.find(rChar) != map.end()) {left = max(left, map[rChar] + 1);}map[rChar] = right;ans = max(ans, right - left + 1);right++;}return ans;}
};
数组
对于数组，解法和 map 其实非常类似。
我们第一反应肯定就是 26 个英文字母，但是由于我们题目中要求了 「s由英文、数字、符号和空格组成」，所以很自然的想法就是 255 来表示 ASCII 码。
同样的，我们在数组中存储的是对应的下标位置。
class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> index(256, -1);int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];if (index[rChar] != -1 && index[rChar] >= left) {left = max(left, index[rChar] + 1);}index[rChar] = right; //还是隐式类型转换ans = max(ans, right - left + 1);right++;}return ans;}
};