美文网首页
无重复字符的最长子串

无重复字符的最长子串

作者: 哦累哇滚筒洗衣机 | 来源:发表于2018-05-14 16:14 被阅读0次

    题目描述

    给定一个字符串,找出不含有重复字符的最长子串的长度。

    示例
    给定 "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
    
            }
        }
    

    这段代码在LeetCode中测试未通过,把LeetCode未通过的测试案列放到本地测试,却又是通过的。所以呢,代码有没有问题,我也不知道啊╮(╯▽╰)╭,如果你找到问题了,请告诉我了。

    相关文章

      网友评论

          本文标题:无重复字符的最长子串

          本文链接:https://www.haomeiwen.com/subject/jvcddftx.html