阅读量:0
力扣题目链接
状态：在本题中，我们可以很明显得看出出现了关键字：子串、最长，所以我们肯定是选用滑动窗口来解决这个题目。
滑动窗口首先要解决的就是我们选择什么样的容器来存储数据呢？本体中是计算重复字符，我们可以使用 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; } }; 