LeetCode(3) 无重复字符的最长子串

xbdyhh · · 603 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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

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

官方解法：

func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[i-1])
        }
        for rk + 1 < n && m[s[rk+1]] == 0 {
            // 不断地移动右指针
            m[s[rk+1]]++
            rk++
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

作者：LeetCode-Solution

个人思路：

func lengthOfLongestSubstring(s string) int {
    m := map[byte]int{}
    n := len(s)
    rk, ans := -1, 0
    var j int 
    j = 0
    ok := false
    for i := 0; i < n&&rk+1 <n; i++ {
        if i != 0 && rk + 1<n {
            i = m[s[rk+1]]+1
        }
        for ;rk + 1 < n;rk++{
            j,ok =m[s[rk+1]]
            if ok&&j>=i{break}
            m[s[rk+1]] =rk + 1 
        }
        if !(ans>(rk - i+1)){ans = rk-i+1}
    }
    return ans
}

思路：rk为右指针，i为左指针，右指针搜寻字符串并且储存字符出现信息，在官方解法中，只储存是否出现，在个人思路中储存字符出现的位置，目的时为了使左指针运动可以不用一个一个遍历删除，实现跳跃式的移动。
速度上并不稳定，个人推测可能与字符串重复度有关，如果重复度高与官方给出的算法区别不大，但是如过重复度低，可以大量减少左字符串遍历字符串的时间。

有疑问加站长微信联系（非本文作者）