本文共 2330 字，大约阅读时间需要 7 分钟。

目录

题目描述

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

输入/输出示例：

解决方案

这个问题本质上是一个队列应用问题。我们依次将元素放入队列中，在入队列的时候检查要入队列的元素是否存在于队列中。如果存在，需要将队列中不断的弹出元素，直到把重复的该元素弹出，然后再将该元素入队列。此外，队列中需要有一个变量记录队列长度的最大值，在所有字符都完成过入队列操作后，将该记录返回。

代码 

package mainfunc lengthOfLongestSubstring(s string) int {	queue := CreateQueue()	for _, char := range s {		queue.Push(char)	}	return queue.MaxLength}type Queue struct {	Base		[]int32	base		map[int32]string	MaxLength	int}func CreateQueue() *Queue {	queue := new(Queue)	queue.base = make(map[int32]string)	return queue}func (q *Queue) Push(data int32) {	if q.Exist(data) {		q.Remove(data)	}	q.Base = append(q.Base, data)	q.base[data] = ""	if q.Length() > q.MaxLength {		q.MaxLength = q.Length()	}}func (q *Queue) Exist(data int32) bool {	_, ok := q.base[data]	return ok}func (q *Queue) Remove(data int32) {	for {		element := q.Pop()		if element == data {			break		}	}}func (q *Queue) Pop() int32 {	element := q.Base[0]	q.Base = q.Base[1:]	delete(q.base, element)	return element}func (q *Queue) Length() int {	return len(q.Base)}

代码走读

package mainimport "fmt"// 解决函数（LeetCode定义）func lengthOfLongestSubstring(s string) int {   queue := CreateQueue()   for _, char := range s {      queue.Push(char)   }   return queue.MaxLength}// 队列结构定义。数据存储在Base中，MaxLength表示最大长度记录type Queue struct {   Base      []int32   base      map[int32]string   MaxLength  int}// 队列初始化func CreateQueue() *Queue {   queue := new(Queue)   queue.base = make(map[int32]string)   return queue}// 往队列中放入一个元素。如果该元素存在，则将该元素和该元素之前的所有元素弹出队列，然后再将该元素放入队列func (q *Queue) Push(data int32) {   if q.Exist(data) {      q.Remove(data)   }   q.Base = append(q.Base, data)   q.base[data] = ""   // 判断长度是否超过了记录最大值   if q.Length() > q.MaxLength {      q.MaxLength = q.Length()   }}// 判断队列是否存在。base的意义在于查询比Base要快func (q *Queue) Exist(data int32) bool {   _, ok := q.base[data]   return ok}// 从队列中弹出指定的元素，弹出的同时也会将该元素之前的所有元素弹出func (q *Queue) Remove(data int32) {   for {      element := q.Pop()      if element == data {         break      }   }}// 从队列头弹出一个元素func (q *Queue) Pop() int32 {   element := q.Base[0]   q.Base = q.Base[1:]   delete(q.base, element)   return element}// 求队列长度func (q *Queue) Length() int {   return len(q.Base)}// 自测用例func main() {   result := lengthOfLongestSubstring("abcabcbb")   fmt.Println(result)}

传送门

转载地址：http://jdsoi.baihongyu.com/