示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"等龙，所以其長(zhǎng)度為 3处渣。>
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1蛛砰。>
解題思路使用注釋標(biāo)注的很詳細(xì)
方法1
func lengthOfLongestSubstring(_ s: String) -> Int {
var maxCount = 0
var currCount = 0
var subString = ""
for a in s {
if subString.contains(a) {
//如果包含則從當(dāng)前該字符的postion開(kāi)始計(jì)算
let range = subString.range(of: String(a))
// subString = String(subString.suffix)
subString = String(subString[(range?.upperBound)!..<subString.endIndex])
}
subString.append(a)//拼接
currCount = subString.count
if currCount > maxCount {
maxCount = currCount
}
}
return maxCount
}
方法2 (更優(yōu))
func lengthOfLongestSubstring(_ s: String) -> Int {
if s.count <= 1 {
//如果小于一個(gè)字符 直接返回
return s.count
}
var ans = 1 //最大長(zhǎng)度, 默認(rèn)為1
var sta = 0 //起始位置
var had = false //是否遇到過(guò)重復(fù)字符, 如果遇到重新判斷一次最大長(zhǎng)度
var cache : [Character : Int] = [:]
var i = 0 //遍歷下標(biāo)
for c in s {
//遍歷字符串 c為字符類(lèi)型
if let temp = cache[c] {
//如果遇到重復(fù)字符
had = true
//保留最大的起始位
sta = max(temp, sta)
print(sta)
ans = max(ans, i-sta)
} else{
//不是重復(fù)字符
if !had, i > 0 {
//一直沒(méi)遇到過(guò)重復(fù)字符執(zhí)行該分支 直接+1
//如果遇到過(guò)重復(fù)字符之后, 則該分支不會(huì)被執(zhí)行
ans += 1
} else {
//獲取最大長(zhǎng)度
ans = max(ans, i-sta)
}
}
//保存最新位置
cache[c] = i
i += 1
}
return ans
}
