# 【基础篇 - Day 22】 2020-11-21 - 3. 无重复字符的最长子串
# 题目描述
# 入选理由
- hashtable 用于空间换时间
# 题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
https://github.com/leetcode-pp/91alg-2/issues/48#issuecomment-731588676
# 解法一
# 时空复杂度
时间复杂度：O(n^2) 虽然感觉最差的情况应该也是几倍 N 没到下个量级 但是怪慢的就当 N^2 了
空间复杂度: O(n) n 是最长子串长度
这代码怪丑的，明天优化一下
var lengthOfLongestSubstring = function (s) {
let maxLength = 0
let count = 0
let map = {}
let i = 0
while (i < s.length) {
if (map[s[i]] != undefined) {
maxLength = Math.max(maxLength, count)
count = 0
i = map[s[i]]
map = {}
} else {
count = count + 1
map[s[i]] = i
}
i++
}
maxLength = Math.max(maxLength, count)
return maxLength
};
# 解法二
# 时空复杂度
时间复杂度：O(n)
空间复杂度: O(n) n 字符种类数
把上面优化了下 做一个 j 标记 到 上一次重复字符串后面一个 开始重新计数
var lengthOfLongestSubstring = function (s) {
let maxLength = 0
let map = {}
for (let i = 0, j = 0; i < s.length; i++) {
if (map[s[i]] != undefined) {
j = Math.max(map[s[i]] + 1, j)
}
maxLength = Math.max(maxLength, i - j + 1)
map[s[i]] = i
}
return maxLength
};