描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

数据范围:s.length≤40000

示例
// 输入:
"abcabcbb"
// 返回值:
3
// 说明:因为无重复字符的最长子串是"abc",所以其长度为 3。

// 输入:
"bbbbb"
// 返回值:
1
说明:因为无重复字符的最长子串是"b",所以其长度为 1。

// 输入:
"pwwkew"
// 返回值:
3
// 说明:因为无重复字符的最长子串是 "wke",所以其长度为 3。
// 请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。
解题思路

滑动窗口

通过 left、right 指针控制左右窗口,长度等于 right - left + 1,右指针依次向右移动

通过 hash(或数组)记录每个字符出现的次数,如果大于 1,则左窗口依次向右移动,直到该字符等于 1 为止

代码实现
/**
 * 滑动窗口
 *
 * @param s string 字符串
 * @return int 整型
 */
func lengthOfLongestSubstring(s string) int {
    n := len(s)
    if n == 1 {
        return 1
    }

    hash := make([]int, 256)
    left, right, max := 0, 0, 1
    for right < n {
        hash[s[right]] += 1
        for hash[s[right]] != 1 {
            hash[s[left]]--
            left++
        }
        max = int(math.Max(float64(max), float64(right-left+1)))
        right++
    }

    return max
}

本文由 一切随风 创作,可自由转载、引用,但需署名作者且注明文章出处。

10 条评论

  1. abdrsolzhs
    abdrsolzhs

    奖励旅程

  2. hmpytovwez
    hmpytovwez

    相声大电影之我要幸福

  3. uajdssstup
    uajdssstup

    午夜迷案

  4. xbvantcomr
    xbvantcomr

    打倒他们

  5. dpsmocrtok
    dpsmocrtok

    私家侦探

  6. edsidlguvx
    edsidlguvx

    鬼屋直播

  7. wiaurwwfcf
    wiaurwwfcf

    再见福宝

  8. ilwosztxig
    ilwosztxig

    反贪风暴5最终章

  9. buhywsjdfa
    buhywsjdfa

    最强壮的人

  10. wmmnfgkhni
    wmmnfgkhni

    误杀2

添加新评论