11--无重复字符的最长子串

Github链接

一、题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

二、思路一： 滑动窗口

// 思路一: 滑动窗口
    func lengthOfLongestSubstring02(_ s: String) -> Int {
        let temp = s + " "
        let arr = Array(temp)
        var left = 0
        var right = 0
        var maxLen = 0
        
        while right < arr.count - 1 { // 最后一个字符遍历不到,所以在前面对s + " "
            let subArr = arr[left...right].map{String($0)}
            maxLen = max(subArr.count, maxLen)
            print("subArr--",subArr)
            //"abcabcbb"
            let nextStr = String(arr[right + 1])
            for i in 0..<subArr.count {
                if subArr[i] == nextStr {
                    left += (i+1)
                }
            }
            right += 1
        }
        
        return maxLen
    }

三、思路二：字典

记录之前出现的下标，[Character: Int]，这种效率比上面的效率高

// 思路二: 字典
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var res = 0
        let arr = Array(s)
        var left = 0
        var dict = [Character: Int]()
        
        //"abcdc"
        for right in 0..<arr.count {
            if let value = dict[arr[right]] { // right = 4 , value = dict[c] = 2
                left = max(value + 1, left) // max(3, 0)
            }
            dict[arr[right]] = right // [[a: 0], [b: 1],[c: 2],[d: 3]]
            res = max(res, right - left + 1)
        }
        
        return res
    }