題目:
給定一個(gè)字符串,找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
示例:
(1)給定 "abcabcbb" ,沒(méi)有重復(fù)字符的最長(zhǎng)子串是 "abc" ,那么長(zhǎng)度就是3。
(2)給定 "bbbbb" ,最長(zhǎng)的子串就是 "b" ,長(zhǎng)度是1。
(3)給定 "pwwkew" ,最長(zhǎng)子串是 "wke" ,長(zhǎng)度是3。請(qǐng)注意答案必須是一個(gè)子串,"pwke" 是 子序列 而不是子串。
func lengthOfLongestSubstring(_ s: String) -> Int {
var ans:Int = 0
let n = s.count
var letters = Set<Character>()
var result = [Int]()
//檢測(cè)數(shù)組中是否包含一個(gè)數(shù)大于了字符串長(zhǎng)度的一半,這樣可以減少時(shí)間復(fù)雜度,定一個(gè)Bool值
var isJumpToEnd = false
for i in 0..<n {
letters.removeAll()
let index = s.index(s.startIndex, offsetBy: i)
letters.insert(s[index])
if isJumpToEnd {
break;
}
for j in i+1...n {
let index2 = s.index(s.startIndex, offsetBy: j)
//采用集合的形式,每次從字符串取出一個(gè)字符,便做一次查詢,沒(méi)有就加進(jìn)去,有的話就記錄數(shù)值,加入數(shù)組,然后開(kāi)啟下一次循環(huán)
if letters.contains(s[index2]) {
ans = j - i
result.append(ans)
if ans >= n/2 {
isJumpToEnd = true
}
break
}else{
letters.insert(s[index2])
}
}
}
var max:Int = result[0]
for index in 0..<result.count {
if result[index] > max {
max = result[index]
}
}
return max
}
以上答案純屬個(gè)人答案,在LeetCode提答案時(shí),報(bào)錯(cuò):超出范圍,檢測(cè)目前的循環(huán)沒(méi)找到越界,暫時(shí)不提了,等再優(yōu)化看看
簡(jiǎn)單描述下個(gè)人思路:
1、利用集合Set去對(duì)字符串中的每一個(gè)Character進(jìn)行操作,不同的進(jìn)行保存,直到碰到相同元素,計(jì)算此時(shí)字符串最大長(zhǎng)度
2、兩次for...in遍歷字符串,進(jìn)行添加集合的Character對(duì)比
3、將每次記錄的字符串最大長(zhǎng)度保存在一個(gè)數(shù)組中,然后從數(shù)組中找尋一個(gè)最大的值,即為字符串的最大長(zhǎng)度返回即可
ps:檢測(cè)數(shù)組中是否包含一個(gè)數(shù)大于了字符串長(zhǎng)度的一半,這樣可以減少時(shí)間復(fù)雜度,定一個(gè)Bool值 isJumpToEnd
利用LeetCode平臺(tái)繼續(xù)深入學(xué)習(xí)swift的語(yǔ)法部分,繼續(xù)加油了!
寫(xiě)的不好,請(qǐng)指教!