前言
水题收割者
正文
问题来源
本问题来自leetcode上的3题。这道题之前做过，这次用go语言再做一遍
问题描述
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。
给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。
给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是子序列 而不是子串。
分析：
暴力解法 C代码如下：
int lengthOfLongestSubstring(char* s) {
int len = 1;
int index = 0;
int comp = 0;
int temp = 0;
int breakFlag = 0;
int longLen =1;
if('\0' == s[index]) return 0;
for(index=0;s[index] != '\0';index++)
{
for(len=1;s[index+len] != '\0';len++)
{
temp = index+len;
for(comp=index;comp < temp;comp++)
{
if(s[temp] == s[comp])
{
breakFlag = 1;
break;
}
}
if(1 == breakFlag)
{
breakFlag = 0;
break;
}
else if(len+1>longLen)
{
longLen = len+1;
}
}
}
return longLen;
}
思路实际上是十分巧妙的，我们事先建立一个数组，用来记录所有字符的出现位置，初试的时候因为我们计数肯定是从第一个字符开始，第一个字符的下标为0，那么我们就就将先将初试的时候各个字符出现的位置设置成-1，那么我们首先从第一个字符开始往后计数，每次发现一个字符就就这个字符出现的位置改成现在的位置，这个时候我们开始计数的位置还是0，一旦我们往后不断更新最大的不重复子字符串的长度的时候，第一个重复的字符出现了，那么这个时候我们就要更新开始的位置了，因为什么呢，因为我们的字符串里不能包含两个相同的字符，因此这个时候只有两种选择：一种是起点选在原来的起点，重点选在两个重复的字符之间，这种情况显然我们已经考虑过了，因此这个时候要做的就是将字符开始的位置搬运到这个重复字符第一次出现的位置之后的那个位置上就可以了。而我们怎么更新这个字符最新出现的位置呢？在一次循环的最后更新就可以了，非常的巧妙。
func lengthOfLongestSubstring(s string) int {
count := 0
var a [256]int
sl := len(s)
for k := 0; k < 256; k++ {
a[k] = -1
}
i, j := -1, 0
for ; j < sl; j++ {
if a[s[j]] > i {
i = a[s[j]]
}
if j - i > count {
count = j - i
}
a[s[j]] = j
}
return count
}
总结：
结语
闲来无事的话，多练习练习，做做题。
