經(jīng)典雙指針
題目描述
給定一個字符串 s 挽荠，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1
輸入： s = "abcabcbb"
輸出： 3
解釋： 因為無重復(fù)字符的最長子串是 "abc"漠另，所以其長度為 3跃赚。
示例 2
輸入： s = "bbbbb"
輸出： 1
解釋： 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1纬傲。
示例 3
輸入： s = "pwwkew"
輸出： 3
解釋： 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3算墨。 請注意领猾，你的答案必須是 子串 的長度，"pwke" 是一個子序列摔竿，不是子串。
示例 4
輸入： s = ""
輸出： 0
提示
0 <= s.length <= 5 * 100,000-
s由英文字母熬苍、數(shù)字袁翁、符號和空格組成
原題目鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
分析
暴力解法（一般通不過）
這個問題的第一個考慮的直接解法是通過兩個for循環(huán)進(jìn)行暴力求解。第一個for循環(huán)i標(biāo)記無重復(fù)子串的起點柄驻，第二個for循環(huán)j標(biāo)記子串的末尾焙压。通過判斷字符串s[i..j]是否是無重復(fù)子串，并和當(dāng)前最長記錄比較來完成算法涯曲。該方案的時間復(fù)雜度是O(n^2)。
但是這個方案在本問題中是不可行的拨黔，因為問題規(guī)模是0 <= s.length <= 5 * 100,000绰沥，如果采用O(n^2)復(fù)雜度基本會超時贺待，并且這也不是最優(yōu)復(fù)雜度态兴。
O(n)雙指針解法
考慮到第一個思路里，用i和j分別標(biāo)記字符串的某段起始和終止位置，遍歷整個數(shù)組甜刻，最終得出數(shù)組的最長無重復(fù)子串的長度值。
那么可以把思路調(diào)整為傻铣，讓原先的兩個循環(huán)改成一個循環(huán)祥绞，只掃描一遍數(shù)組即可完成所有無重復(fù)子串的查找。
基本思路原則是這樣的：
- 給定兩個字符串索引
i和j蜕径，且j始終大于i。
- 每次循環(huán)保證字符串子串
s[i..<j]始終為一個無重復(fù)子串梦染。
- 始終保證循環(huán)過程中朴皆，
i在需要調(diào)整時往終點移動一或者若干位，j往終點移動一位遂铡。
- 當(dāng)
j移動到字符串末尾時，算法結(jié)束伪货。
- 保證循環(huán)結(jié)束時珠增，算法能找到所有的無重復(fù)字子串。
為此蒂教，我們用非形式化的循環(huán)不變式來描述一下該算法的執(zhí)行。
首先是初始化懊悯，當(dāng)i = 0且j = 1時，由于s[i..<j]只有一個字符s[0]桃焕，單個字符肯定是一個無重復(fù)子串捧毛。
接下來，我們假設(shè)s[i..<j]是一個無重復(fù)子串呀忧。那么接下去我們要檢查的情形是。
- 當(dāng)
s[j]所包含的字符在s[i..<j]中并不存在時胰坟，則s[i..<j+1]必然也是無重復(fù)子串泞辐。
- 當(dāng)
s[j]所包含的字符在s[i..<j]中存在時新锈，假定存在的沖突位置為k，則s[k] == s[j]落午，則s[k+1..<j+1]是新的待掃描的無重復(fù)子串瑰煎。
當(dāng)j為字符串最后一個字符時撇吞，我們已經(jīng)掃描了所有無重復(fù)子串。
那么牍颈，算法在執(zhí)行過程中只要不斷的保存最大的無重復(fù)子串長度即可。
這里就存在一個問題讥蔽，當(dāng)已知s[i..<j]為無重復(fù)子串時画机，我們?nèi)绾沃?code>s[j]的字符在s[i..<j]中存不存在？
留意問題的輸入范圍步氏，我們看到
`s` 由英文字母、數(shù)字芋类、符號和空格組成
由于s 由英文字母、數(shù)字侯繁、符號和空格組成，那就意味著字符串的內(nèi)容是有ascii字符組成丽焊，我們完全可以用一個容量為128的數(shù)組來保存每個字符的位置信息咕别。
具體來講就是，我們用數(shù)組cache保存字符的ascii碼在字符串的最近一次掃描索引信息顷级，舉例來說确垫，就是當(dāng)掃描字符串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 {
// 當(dāng)cache保存的字符位置在范圍內(nèi)，說明出現(xiàn)字符沖突
// 調(diào)整 i 讓它往前跳
i = k + 1
}
cache[Int(cs[j])] = j
j += 1
// i被調(diào)整過后幔妨，或者沒有沖突字符谍椅，新子串也是無重復(fù)子串
m = max(m, j-i)
}
return m
}
}
