Loveyless的学习笔记哈哈
我怎么这么菜 看着我写了半天的代码跑出了这么个<<好成绩>> 我开心的流下了眼泪 
想法思路
本来我第一想到的思路就是(滑动窗口)我后来才知道叫这个名字
代码
自己写的 看起来有点傻瓜式 速度也慢的一批
go
func lengthOfLongestSubstring(str string) int {
tempString := ""
stringLength := 0
for i := 0; i < len(str); i++ {
for j := i; j < len(str); j++ {
//如果有重复的字符
if strings.Contains(tempString, string(str[j])) {
if len(tempString) > stringLength {
stringLength = len(tempString)
}
// tempString = string(str[j])
tempString = ""
break
} else {
tempString += string(str[j])
}
// 运行到最后一位 长度给进去
if j == len(str)-1 {
if len(tempString) > stringLength {
stringLength = len(tempString)
}
}
}
}
return stringLength
}
题解
看了这个视频讲解的滑动窗口 貌似比我写的速度会快一点 啃了一下
就是说 js 好方便 go 的字符串数组处理函数都需要自己封装(也可能是我刚学 go 不知道那么多 api)
但是最后的成绩也是不尽人意(但是比我自己写的好多了 但是感觉代码有点多 需要仔细看一会 但是 up 主的视频很好理解)
go
// 切片中是否存在
func has(list []string, str string) bool {
for _, v := range list {
if v == str {
return true
}
}
return false
}
// 切片中子项的下标
func sliceIndex(list []string, str string) int {
for i, v := range list {
if v == str {
return i
}
}
return -1
}
func lengthOfLongestSubstring(s string) int {
// 左指针 右指针 长度 最大长度
left, right, length, maxLength := 0, 0, 0, 0
// 表
set := make([]string, 0)
// 滑动是通过右指针一直向右滑动来实现的 所以右指针不能超过字符串长度
for right < len(s) {
// 如果右指针不在表中 则 更新长度 更新最大长度 右指针向右滑动
if !has(set, string(s[right])) {
set = append(set, string(s[right]))
length++
if length > maxLength {
maxLength = length
}
// 右指针向右滑动
right++
} else {
// 如果右指针指向的值在表中 则 删除表中左指针指向的值 左指针向右滑动
for has(set, string(s[right])) {
i := sliceIndex(set, string(s[left]))
set = append(set[:i], set[i+1:]...)
left++
length--
}
// 直到右指针指向的值不在表中 则 添加右指针的值 左指针向右滑动
set = append(set, string(s[right]))
length++
right++
}
}
return maxLength
}
题解 2
又找到一位大佬的题解 代码简洁 速度飞快
作者：bananajin-6
首先，定义变量 start 当前子串的左边界，tmp 记录当前子串的长度，res 保存可能最后的结果。
1）确定右边界 确定规则：满足题意的最长子串右边界需要比较从左边界开始的所有字符是否有相同，如果都不相同，则计算出该子串的长度，需要注意的长度计算公式是，tmp = i - start + 1 ； 同时，不难发现右边界的确定只需要遍历一遍字符串即可。
2）确定左边界 左边界的确定，特别需要注意的是，如果在遍历右边界的时候，出现当前子串不满足题意，即子串中（除去右边界）存在和右边界相同，这时候，左边界是根据重复字符所在位置确定的，如果我们直接把左边界移到当前子串右边界的位置，则是不可以的，当然如果直接移动一位，也导致时间的浪费。 容易找出这样的例子 abedfbcg，在上面的字符串中，可以发现位置 2，5 存在相同字符 b，那如果使用刚刚说的子串左边界移动的方法，显然会得到错误的答案，最长子串 bedf；可是最长子串应该是 edfbcg。
3）确定是否是最长子串 在解决了上面左右边界的确定，这个步骤是相对容易很多的，其实只需要比较当前子串长度是否比之前确定的满足题意的子串更长。 当然里面也有一点需要注意，就是如果当前子串不满足题意，此时需要将子串的长度置为 tmp = i - start。
i 相当于右边界，j 相当于左边界，巧妙用遍历右边界嵌套左边界，利用 i-start+1 的差值作为移动窗口的最大长度。逆向思维很好(我怎么觉得我就是这么写的)
go
func lengthOfLongestSubstring(s string) int {
//start当前子串的左边界，tmp记录当前子串的长度，length保存可能最后的结果。
start, tmp, length := 0, 0, 0
for i := 0; i < len(s); i++ {
tmp = i - start + 1
for j := start; j < i; j++ {
// 如果有重复的字符
if s[i] == s[j] {
// 记录字串的长度
tmp = i - start
// 重置左边界
start = j + 1
break
}
}
// 保存最大值
if tmp > length {
length = tmp
}
}
return length
}