目录

最长不含重复字符的子字符串

杨浩成收录于算法

2020-08-24 约 325 字预计阅读 1 分钟次阅读

目录

1. 题目

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

1
2
3
4
5


示例 1:

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

2.算法

2.1.算法要点&图解

map[key]value key不可重复，定义lastOccurred来记录每个字符的最后出现位置

Start 记录开始的位置，遇到重复则更新start = lastI + 1

2.2 算法文字描述

最后一步更新lastOccurred[x]有两种情况

1.key 存在，即单词存在，更新它的最后出现位置
2.key不存在，即单词未出现，则新建

3.代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func lengthOfLongestSubstring(s string) int {
    lastOccurred := make(map[byte]int)
    start := 0
    maxLength := 0

    for i,ch := range []byte(s){ 
        if lastI,ok := lastOccurred[ch];ok && lastI >= start{
            start = lastI + 1
        }
        if i - start + 1 > maxLength{
            maxLength = i - start + 1
        }
        lastOccurred[ch] = i
    }
    return maxLength
}