经典双指针
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1
输入： s = "abcabcbb"
输出： 3
解释： 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2
输入： s = "bbbbb"
输出： 1
解释： 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3
输入： s = "pwwkew"
输出： 3
解释： 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4
输入： s = ""
输出： 0
提示
0 <= s.length <= 5 * 100,000-
s由英文字母、数字、符号和空格组成
原题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
分析
暴力解法（一般通不过）
这个问题的第一个考虑的直接解法是通过两个for循环进行暴力求解。第一个for循环i标记无重复子串的起点，第二个for循环j标记子串的末尾。通过判断字符串s[i..j]是否是无重复子串，并和当前最长记录比较来完成算法。该方案的时间复杂度是O(n^2)。
但是这个方案在本问题中是不可行的，因为问题规模是0 <= s.length <= 5 * 100,000，如果采用O(n^2)复杂度基本会超时，并且这也不是最优复杂度。
O(n)双指针解法
考虑到第一个思路里，用i和j分别标记字符串的某段起始和终止位置，遍历整个数组，最终得出数组的最长无重复子串的长度值。
那么可以把思路调整为，让原先的两个循环改成一个循环，只扫描一遍数组即可完成所有无重复子串的查找。
基本思路原则是这样的：
- 给定两个字符串索引
i和j，且j始终大于i。
- 每次循环保证字符串子串
s[i..<j]始终为一个无重复子串。
- 始终保证循环过程中，
i在需要调整时往终点移动一或者若干位，j往终点移动一位。
- 当
j移动到字符串末尾时，算法结束。
- 保证循环结束时，算法能找到所有的无重复字子串。
为此，我们用非形式化的循环不变式来描述一下该算法的执行。
首先是初始化，当i = 0且j = 1时，由于s[i..<j]只有一个字符s[0]，单个字符肯定是一个无重复子串。
接下来，我们假设s[i..<j]是一个无重复子串。那么接下去我们要检查的情形是。
- 当
s[j]所包含的字符在s[i..<j]中并不存在时，则s[i..<j+1]必然也是无重复子串。
- 当
s[j]所包含的字符在s[i..<j]中存在时，假定存在的冲突位置为k，则s[k] == s[j]，则s[k+1..<j+1]是新的待扫描的无重复子串。
当j为字符串最后一个字符时，我们已经扫描了所有无重复子串。
那么，算法在执行过程中只要不断的保存最大的无重复子串长度即可。
这里就存在一个问题，当已知s[i..<j]为无重复子串时，我们如何知道s[j]的字符在s[i..<j]中存不存在？
留意问题的输入范围，我们看到
`s` 由英文字母、数字、符号和空格组成
由于s 由英文字母、数字、符号和空格组成，那就意味着字符串的内容是有ascii字符组成，我们完全可以用一个容量为128的数组来保存每个字符的位置信息。
具体来讲就是，我们用数组cache保存字符的ascii码在字符串的最近一次扫描索引信息，举例来说，就是当扫描字符串abc的时候，c在位置2，那么有cache[c.ascii] = 2。
注：
ascii编码为8位，所以容量仅为128。
swift题解源码及注释
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
// 算法边界不包含空字符串，判定返回
guard !s.isEmpty else { return 0 }
let cs = s.cString(using: .ascii)!
let len = strlen(cs)
// 初始化i和j
var i = 0
var j = 1
// cache存放遍历字符的位置
var cache: [Int] = Array(repeating: -1, count: 128)
var m = j - i
// cache保存着第一个字符的位置
cache[Int(cs[i])] = i
while j < len {
let k = cache[Int(cs[j])]
if k >= i {
// 当cache保存的字符位置在范围内，说明出现字符冲突
// 调整 i 让它往前跳
i = k + 1
}
cache[Int(cs[j])] = j
j += 1
// i被调整过后，或者没有冲突字符，新子串也是无重复子串
m = max(m, j-i)
}
return m
}
}
