3. 无重复字符的最长子串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。s由英文字母、数字、符号和空格组成
示例一：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例二：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例三：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例四：
输入: s = ""
输出: 0
解题方法：滑动窗口
class Solution {
func getChar(_ s: String, at offset: Int) -> Character {
let index = s.index(s.startIndex, offsetBy: offset)
return s[index]
}
func lengthOfLongestSubstring(_ s: String) -> Int {
let length = s.count
guard length >= 2 else { return length }
var map = [Character: Int]()
var start = 0
var result = 0
for end in 0..<length {
let char = getChar(s, at: end)
if let index = map[char] {
start = max(index, start)
}
map[char] = end + 1
result = max(end - start + 1, result)
}
return result
}
}
解题思路
这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
复杂度分析
- 时间复杂度：
O(N)，其中N是字符串s长度。 - 空间复杂度：
O(∣Σ∣)，其中Σ表示字符集（即字符串中可以出现的字符），∣Σ∣表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有ASCII码在 [0,128) 内的字符，即∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣个，因此空间复杂度为O(∣Σ∣)。