Go 无重复最长子字符串
一个字符串 找出其中不含有重复字符的 最长子串 及其长度
示例
输入 "abcabcbb"
输出 3
因为无重复字符的最长子串是 "abc" 所以其长度为 3
输入 "bbbbb"
输出 1
因为无重复字符的最长子串是 "b" 所以其长度为 1
遍历字符串找不同可以先排序吗
不可以 在题目的要求下 无重复的最长子串必须是连续的在原来的字符串顺序保持不变的情况下
如何判断字符串中不重复
Golang中strings包的Contain函数判断 原序列是否包含子序列
假设字符串长度为0 返回值应该为0
假设字符串长度为1 返回值为1
假设字符串长度为2 需要将第2个字符和第一个字符作比较 是否重复 如果重复 最长的长度为1不变 如果不重复 最长的长度需要进行+1
规律 假定最长长度max为1 即是第一个字符 然后找第二个字符 如果不相同 则max+1
以此类推 每次遍历一个字符 需要和前面的字符串比较 然后让max持续+1
如果遇到相同的 说明从第一个字符到当前已经找到了当前的最大值
此时应该从第二个字符往后一直找不同
如果在找的过程中发现组合的字符串长度大于了max
此时应该让max等于当前字符串的长度
为了可以让字符可以找到下次应该循环的位置
因此需要定义一个移动的指针
代码思路
1 判断字符串长度是否为0 如果为0直接返回0
2 假设max为1 substr(含有最长长度的字符串)对应第一个字符 指针指向第一个字符
3 遍历字符串
4 substr进行追加下一个字符
5 判断该substr的最后一个字符 是否与前面的字符串重复
6 如果不重复 判断max是否小于当前的substr 如果小于 进行重新赋值max长度为len(substr)
7 如果重复 指针指向下一个字符 substr等于该字符 进行重新寻找连续的不重复的字符串
package main
import (
"fmt"
"strings"
)
func Same(s string) bool {
if strings.Contains(s[:len(s)-1], s[len(s)-1:]) {
return true
}
return false
}
func lengthOfLongestSubstring(s string) (max int,returnstr string) { //寻找不重复最长字符串
if len(s) == 0 {
return 0,""
}
returnstr = "";
substr := s[:1] // 定义一个字符串数组存放结果
max = len(substr)
start := 0
for i := 1; i < len(s); i++ {
substr += string(s[i])
if Same(substr) {
start ++
i = start
substr = string(s[i])
} else {
if len(substr) > max {
max = len(substr)
returnstr = substr
}
}
}
return max,returnstr
}
func main() {
//fmt.Println(lengthOfLongestSubstring("")) //0
fmt.Println(lengthOfLongestSubstring("lingnamagan20132019"))
}
尊贵的董事大人
英文标题不为空时 视为本栏投稿
需要关键字 描述 英文标题