LeetCode|无重复字符的最长子串

今天的题目为：

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

首先来思路分析：

我们可以先第一次把所有不重复的字符串分割一下保存下来，这样就可以找到这一次的不重复的子字符串最长的

然后在一次一次往后面移动，这样就可以找出所有不重复的子字符串，最后再求出最大值。

比如：

abcd ahjiklo字符串我们第一次从头开始寻找，找到不重复的子字符串，那就有两个，一个为abcd另外一个为ahjiklo,如果单单重上面看那么最长的不重复子字符串就是ahjiklo，但是我们需要的不是这个，那么我们就需要再循环一次，每次把第一个字符去掉然后再寻找，比如这一次把a去掉那么找出的最长子字符串就是bcdahjiklo，这个是最长的，然后再把本次的第一个字符去掉一直循环，这样到最后找出最长的子字符串，

复杂度分析：

当然，这种方法可以算是一种暴力解决的方法，没有什么技巧性，时间复杂度也是最复杂的，O（n3）的复杂度，当然如果想要优化的话可以自己去研究一下奥。

代码：

package main

import "fmt"

func lengthOfLongestSubstring(str string) int {   //每次求出的最大值返回
	s:=[]byte(str)          //先把字符串转为byte类型的切片
	slice:=make([]string,0)//ased//aerfch//risdud   //定义一个字符串切片，可以把无重复的字符串字段保存进去
flag:
	for i:=0;i<len(s);i++{

		for j:=i-1;j>=0;j--{
			if s[i]==s[j]{       //这里遍历用来找出无重复字符串段
				slice=append(slice,string(s[:i]))  //把无重复字符段放切片里面去
				s=s[i:]                      //切片往后移
				goto flag;               //在新切片里面再次循环直到找出无重复字符段放进字符串切片里面
			}
		}
	}
	slice=append(slice,string(s))  //把最后一个放进切片，如果整个字符串都没有重复那么就这一个
	//fmt.Println(slice)
	max:=len(slice[0])
	for k:=0;k<len(slice);k++{     //循环找出这一次的最大值
		if len(slice[k])>max{
			max=len(slice[k])
		}
	}
	return max            //返回本次最大值
}
func main(){
	var str string
	fmt.Printf("请输入一个字符串\n")
	fmt.Scanf("%s",&str)
	var max int
	for i:=len(str);i>0;i--{
		tmp:=lengthOfLongestSubstring(str)  //每求一次最大值往后退一次，确保能得到真正的最大值
		if tmp>max{
			max=tmp
		}
		str=str[1:]              //每次用切片割掉第一个元素

	}

	fmt.Println(max)    //输出最大值，这里也可以输出最长的子字符串
}

这样就可以求出来了，如果想要优化的伙伴可以自己去稍加研究。