无重复字符的最长字串

leetcode地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目描述：

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

示例：

输入: "abcabcbb"

输出: 3

解决思路：

使用map lastOccured[byte]int 记录字符和字符最后出现的下标

对于字符串每个字符x：

1.lastOccured[x]不存在或者小于start时不做操作。

2.lastOccured[x]>=start 时，start = lastOccured[x]+1。

3.每次都要更新lastOccured[x],更新最大长度maxLength。

代码如下：

func lengthOfLongestSubstring(s string) int {

    lastOccured := make(map[byte]int)

    start :=

    maxLength :=

    for i, ch := range []byte(s){

        if num, ok := lastOccured[ch]; ok&& num >= start{

            start = num +

        }

        if i-start+ > maxLength{

            maxLength = i-start+

        }

        lastOccured[ch] = i

    }

    return maxLength

}

巴特西

QA:无重复字符的最长子串

无重复字符的最长字串

最新文章

热门文章