1.题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
2.示例
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串
示例 4:
输入: s = "" 输出: 0
3.题目分析
（1）该问题的暴力解法是：设置一个已访问集合，从第一个元素开始，每访问一个元素，就判断它是否已经存在于已访问的集合中。如果未访问则将其加入到已访问的集合中，
如果已访问则证明当前字串出现重复元素，则记录此时的最大长度，再回溯到第一次访问的元素的后一个元素，依次类推直到整个字符串访问结束。
（2）上述解法容易想到，但是效率不高。为了提高效率，进行改进。即——不回溯。每次除了记录第一个加入到已访问的集合的元素，同时记录已访问的集合中是哪一个元素出现重复，
出现重复的以后的元素全部是未重复元素，则此时刷新最大长度，清空已访问集合，下一次开始的元素即从重复的元素的后一个开始即可。
（3）除上述避免回溯的方法之外，每次新的记录时，还可以将未访问的元素长度和当前已得到的最大长度比较，如果未访问的元素长度小于等于已得到的最大长度，那么后面将不需再
比较。因为即使后面的全部是未重复元素，那么它的长度也不会超过当前已经得到的最大长度。
4.给出代码
class Solution { public: int lengthOfLongestSubstring(string s) { int startPos = 0; //每次开始的起始下标 int maxLength = 0;//最大长度 int tempMaxLength = 0;//临时最大长度 vector<int> *visitedSet = new vector<int>;//已访问的元素的下标 A:while(startPos<s.length()){ //判断当前元素是否和已访问集合中的某元素重复 for(int i=0;i<visitedSet->size();i++){ //出现重复，则下一次开始的位置是重复位置的后一个 if(s.at(startPos)==s.at(visitedSet->at(i))){ startPos = visitedSet->at(i)+1; visitedSet->clear(); if(tempMaxLength>maxLength) maxLength = tempMaxLength; tempMaxLength =0; if(s.length()-startPos+1<=maxLength) startPos = s.length()-1; goto A; } } //未出现重复 visitedSet->push_back(startPos); startPos++; tempMaxLength++; } if(maxLength<tempMaxLength) maxLength = tempMaxLength;//说明最后一次长度最大，没有经过重复。 return maxLength; } };
5.总结
（1）代码急于实现，导致代码逻辑不够清晰
（2）虽然相较于暴力解法，时间复杂度有所降低，但是时间效率仍不高。主要浪费在每次和已访问集合的查重上。
（3）如果想让时间复杂度进一步降低，则需要思考如何不每次遍历查重，可以直接和对应的比较。
（4）最后，需要注意不以出现重复为最大长度的情况。