请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例：
输入:
"abcabcbb"'
输出:3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。
来源：剑指Offer第48题
相关企业：
| 公司 | 出现时间 |
|---|---|
| 美团外卖 | 2020.03 |
| 字节跳动 | 2020.03 |
解法一：滑动窗口 + 双指针
时间复杂度：O(n**2)
空间复杂度：O(1)
思路：
- 设定两个指针
low和high分别指向窗口的尾部和头部 - 分情况解决,其实本质是动态规划的思路:
1.如果当前字符不在滑动窗口内的时候,比较之前的存储的最大结果与当前的滑动窗口的大小,取最大的
2.如果当前字符在滑动串口内时,将low指针向前移直到当前字符不在滑动窗口内
代码：
def lengthOfLongestSubstring(self, s: str) -> int:
result, low = 0, 0
for high in range(len(s)):
if s[high] not in s[low:high]:
result = max(high-low + 1, result)
else:
while s[high] in s[low:high]:
low += 1
return result
解法二：滑动窗口 + 哈希表
时间复杂度：O(n)
空间复杂度：O(n)
思路：
上面的代码我们可以看到,当字符在滑动窗口内的时候,我们还需要进行一次遍历,如果我们早在之前就记录下来了字符的位置,通过直接查找,是不是会节省很多时间呢?
我们想到了使用哈希表,因为它的存储和查找的时间复杂度都为O(1)
与上面相比较是利用空间换取了时间
代码：
def lengthOfLongestSubstring(self, s: str) -> int:
dic, low, result = {}, 0, 0
for i in range(len(s)):
if s[i] in dic:
low = max(dic[s[i]] + 1, low)
dic[s[i]] = i
result = max(result, i - low + 1)
return result
