题目描述
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是 3；
给定 "bbbbb" ，最长的子串就是 "b" ，则长度是 1；
给定 "pwwkew" ，最长子串是 "wke" ，则其长度是 3。
请注意答案必须是一个子串，"pwke" 是子序列，而不是子串。
问题分析
本题是一个字符串处理问题，首先我们明确知道问题的求解是最长不重复子串长度，最长不重复子串可能有多个，如上面示例3，而最长不重复子串长度只有一个唯一的值。本题如果通过暴力求解很容易做出，但是时间复杂度比较高，下面我们将从多个角度一一分析。
解决思路一
使用暴力求解法，通过两层循环，内层循环统计从当前字符开始最长不重复子串长度，外层循环比较从不同字符开始最长子串长度，保存最大的长度。
代码实现：
复杂度分析：
时间复杂度：上面使用了两层循环，复杂度达到O(n2),而每次判断子串是否为重复串的复杂度为O(n)，因此算法的时间复杂度为O(n3)。
空间复杂度：在判断子串是否为重复串的时候使用了辅助集合hash_set，它的容量最大为字符串长度或26（英文字母数）的最小值，因此空间复杂度为O(min(n,26))。
算法优化：
上面的算法时间复杂度比较高，但是在此基础上可以稍微优化一些，我们可以在程序中增加两个条件判断语句可以提前结束循环：
当前搜索字符到字符串结尾长度小于等于当前以获取最大长度maxLen时，这时候maxLen即为算法的结果，可以直接返回结果，如上面第四轮后面长度为3
当内层循环已经检索到字符串尾部时，证明最长无重复子串已经获取，可以直接返回结果，如上面第四轮红色箭头访问到字符串结尾时，本次循环结束后则可直接返回。
解决思路二
上面的算法每一轮只移动一个字符，是不是要挨个字符作为子串首字符一一判断呢？我们看下面情况，当在位置5出现重复字符x时，我们在重复字符x（位置2）之前搜索仍然会在位置5处重复，因此我们可以把上一个重复字母的index+1(即图中的3)作为新的搜索位置，这样我们每次只需改变新的开始索引位置（即图中橘黄色箭头），而当前搜索位置（即图中绿色箭头）不用变，继续往下搜索，因此效率大大提升。
复杂度分析
时间复杂度：上面只使用了一层循环，因此时间复杂度为O(n)。
空间复杂度：上面使用了一个辅助数组记录字符上一次出现的位置，大小固定为26，因此空间复杂度为O(1)。
閱讀更多 領釦網 的文章
