题目描述
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例
给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。
给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。
给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。
分析
创建一个指针start
, 用于记录当前子串的开始索引位置,当出现重复字符的时候,就需要把这个指针移动到上一次该字符出现的 index + 1
的位置,作为新的开头,那么在之前的字符就应该舍弃了,所以需要判断一下,每次取得字符是不是在start
之后的。
创建一个参数subMax
,用于记录当前子串的长度
创建一个用于存放字符最后出现的索引位置的字典,key
是字符,value
是字符的索引,需要更新字符最后出现的索引
代码如下:
func lengthOfLongestSubstring(_ s: String) -> Int {
if s.count == 0 {
return 0
}else{
var start = 0 //当前子串的位置
var max = 0 //记录当前
var subMax = 0
var namesOfIntegers = [Character: Int]()
for (index, value) in s.enumerated(){
//如果检索位置的字符第二次出现,记录当前的子串的长度,然后将start移动到之前重复字符的索引+1的位置,记录此时的长度,在下次遇到重复的字符的时候,再次比较长度
if namesOfIntegers.keys.contains(value) && namesOfIntegers[value]! >= start{
max = max > subMax ? max : subMax
start = namesOfIntegers[value]! + 1
subMax = index - start + 1
}else{
subMax += 1
}
namesOfIntegers[value] = index //将为重复的字符序号放入字典
}
return max > subMax ? max : subMax
}
}
网友评论