LeetCode Golang 3. 无重复字符的最长子串

3. 无重复字符的最长子串

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

示例 1:

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

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

方法一: 暴力法  时间复杂度 n3

package main

import (
"fmt"
"strings"
) //给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
// 思路 : 找出全部的无重复子串, 统计出最长的
func lengthOfLongestSubstring(s string) int {
count := 0
sonStringMap := make(map[string]int)
// sonString := []string{""}
for j:=0;j<len(s);j++{
tmpString := s[j:]
subString := ""
for k,v := range []byte(tmpString){
if strings.Contains(subString,string(v)) {
sonStringMap[subString]++
if k == len(tmpString) {
sonStringMap[subString]++
}
subString = ""
} else {
subString += string(v)
if k == len(tmpString)-1 {
sonStringMap[subString]++
}
}
}
}
fmt.Println(sonStringMap)
for k,_ := range sonStringMap {
if count < len(k){
count = len(k)
}
}
return count
} func main() {
s := "alqebriavxoo"
fmt.Println(lengthOfLongestSubstring(s))
}

官方题解:

思路: 如果 s[j]s[j] 在 [i, j) 范围内有与 j' 重复的字符,我们不需要逐渐增加 i 。 我们可以直接跳过 [i,j'] 范围内的所有元素,并将 i 变为 j' + 1。

func lengthOfLongestSubstring(s string) int {
n := len(s)
ans := 0
subMap := make(map[byte]int)
for i, j := 0, 0; j < n; j++ {
if v, ok := subMap[byte(s[j])]; ok {
if i < v {
i = v
}
}
if ans < (j - i + 1) {
ans = j - i + 1
}
subMap[byte(s[j])] = j + 1
}
return ans
}

 LeetCode关于窗口的解释:

LeetCode Golang 3. 无重复字符的最长子串

上一篇:【Derby 系列】Apache Derby 功能特点


下一篇:poj 2777 Count Color(线段树 区间更新)