描述

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

数据范围:

 s.length≤40000 s.length≤40000

示例1

输入：

"abcabcbb"

返回值：

3

说明：

因为无重复字符的最长子串是"abc"，所以其长度为 3。    

示例2

输入：

"bbbbb"

返回值：

1

说明：

因为无重复字符的最长子串是"b"，所以其长度为 1。    

示例3

输入：

"pwwkew"

返回值：

3

说明：

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。    

一、 滑动窗口

Go">package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 滑动窗口* @param s string字符串* @return int整型*/
func lengthOfLongestSubstring(s string) int {// write code hereif len(s) == 0 {return 0}charIndex := make(map[byte]int)maxLen, start := 0, 0for i := range s {char := s[i]if idx, found := charIndex[char]; found && idx >= start {// 当前字符如果出现过，并且它的上一次出现位置在当前起点之后start = idx + 1}// 更新字符的最新位置charIndex[char] = i// 更新最大长度if i-start+1 > maxLen {maxLen = i - start + 1}}return maxLen
}

 二、动态规划

Go">package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @return int整型*/
func lengthOfLongestSubstring(s string) int {// write code hereif len(s) == 0 {return 0}// dp[i] 表示以 s[i] 结尾的最长无重复子串长度dp := make([]int, len(s))// lastIndex 记录字符上一次出现的位置lastIndex := make(map[byte]int)dp[0] = 1           // 第一个字符子串长度为1lastIndex[s[0]] = 0 // 记录第一个字符的位置maxLen := 1         // 记录全局最长子串长度for i := 1; i < len(s); i++ {lastPos, found := lastIndex[s[i]]if found && lastPos >= i-dp[i-1] {// 如果字符在 dp[i-1] 子串内出现过dp[i] = i - lastPos} else {// 如果没有出现过或者不在 dp[i-1] 子串内dp[i] = dp[i-1] + 1}// 更新字符位置lastIndex[s[i]] = i// 更新最大长度if dp[i] > maxLen {maxLen = dp[i]}}return maxLen
}