【算法】Longest Substring Without Re

作者: 无良剑染 | 来源:发表于2020-04-22 19:18 被阅读0次

    题目

    Given a string, find the length of the longest substring without repeating characters.

    Example 1:

    Input: "abcabcbb"
    Output: 3
    Explanation: The answer is "abc", with the length of 3.
    Example 2:

    Input: "bbbbb"
    Output: 1
    Explanation: The answer is "b", with the length of 1.
    Example 3:

    Input: "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3.
    Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

    给出一个字符串,求出最长的无重复字符的子串的长度。

    解题思路

    滑动窗口:

    1. 移动窗口的右边界 right
    2. map 中寻找 right所指字符 chare
      • 找到则说明为重复字符,取 map[chare] + 1left 较大值,更新窗口左边界 left
      • 没找到则将 chare 和索引 right 加入到 map
    3. right - left + 1res 较大值,更新结果 res

    代码实现

    Runtime: 36 ms
    Memory: 21.6 MB

    func lengthOfLongestSubstring(_ s: String) -> Int {
            //字符串长度小于 2 时,直接返回字符串长度
            let sCount = s.count
            if(sCount < 2){
                return sCount
            }
            var res = 0,left = 0
            var sArr = Array(s)
            var map = [Character:Int]()
            //遍历字符串
            for right in 0 ..< sCount{
                //获取 right 所指字符 chare
                let chare = sArr[right]
                //若 map 中含有 chare,则更新 left
                if let rIdx = map[chare] {
                    left = max(left, rIdx + 1)
                }
                //将 chare 和 right 加入到 map 中
                map[chare] = right
                //更新 res
                res = max(right - left + 1, res)
            }
            return res
        }
    

    代码地址:https://github.com/sinianshou/EGSwiftLearning

    相关文章

      网友评论

        本文标题:【算法】Longest Substring Without Re

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