字符串中无重复的最长字串的长度_字符串中不含有重复字符的最长子串的长度。

题目来自LeetCode算法题，难度为中等，解法参考了全站排名
16251的pinku-2大神，废话不多说，下面是干货。
Ps:因为本人是学C++的，所以以后的解法都会用C++或C语言，以后就不再多说了。

题目

给定一个string类型的字符串，请你找出其中不含有重复字符的 最长子串 的长度。
如：给定字符串 “abcbdef” ,其中最长字串是"bdef"，那么输出就为4；

嵌套for循环的方法由于复杂度高，且技术含量较低，就不再赘述，下面给出大佬们提出的三种高级一点的解法。

解法1：滑动窗口

滑动窗口法是一个形象的比喻，大概意思是用一个长度不大于字符串的类似于窗口的边界卡在字符串中间，并在窗口内进行相应的比较。具体的解题过程，我根据大神的讲解，自己又琢磨了一遍，手画了一下。
字符串的存储方式是单字符存储的，算法流程如下：
Step1:在字符串"abcbde"中，令start=0,end=1,去检索第一个字符与第二个字符是否相等，如果不相等，就将end++，length++并记录到result中，然后进入下一次循环；
Step2:此时start不变,end=2,即将前两个字符分别于第三个字符比较，仍然不相同，那么就继续end++,length++并记录到result中；
Step3：此时start不变，end=3，即将前三个字符与第四个字符比较，当for循环到第二个字符’b’时，其与第四个字符相同，那么就将搜索的前边界，即窗口的前端移动至第二个字符’b’的后一位，即start=i+1;然后跳出循环并令length=end-start=1,然后令end++,length++,此时length=2而之前result=3,取最大值后result不变，即length记录当前长度,result记录历史最长长度.
Step4：按照以上能找到相同字符和不能找到相同字符的方法，进行循环，直到条件不满足while，就跳出循环，并返回result就是最终结果。

int lengthOfLongestSubstring(string s) 
{
        //方法1：滑动窗口
        int size=(int)s.size();//获取字符串长度
        int start=0,end=0,length=0,result=0;//start标记起始位置，
        //end标记终止位置，length记录当前无重复字串的长度，
        //result记录长度最大值，即最后结果
        while(end<size)//字符串长度上限为循环的条件
        {
            char temple = s[end];//从第一个字符开始，配合后面的++end，
            //将终止的边界设置为每个字符，依次遍历
            for(int i=start;i<end;i++)//从当前起始到当前终止进行检查
            {
                if(temple==s[i])//如果i位置的字符和当前的s[end]相同，说明前面
                //有一个字符与当前s[end]重复，
                {
                    start = i+1;//那么就将开始边界start移动至i的后一个字符
                    length = end-start;//对应的长度也发生变化
                    break;
                }
            }
            ++end;//每循环一次，向后检索一个字符，直到不满足循环条件退出循环
            ++length;
            result = max(result,length);//看当前长度和记录的历史最大长度result
            //哪个大，就取最大值
        }
         return result;//返回无重复字符串的最大值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解法2：利用哈希表

理解了解法1，那么解法2也可以迎刃而解。解法2最不同的地方就是
由于哈希表的存在，每循环一次，如果当前字符不在哈希表中，说明字符没有重复出现过，那就将该字符记录进哈希表，并进行下一轮循环；而如果在哈希表中已经有该字符，那就将start的位置改为表中重复字符的后一个，并重新计算长度，最后更新该重复字符在哈希表中的映射关系，即将当前字符的索引作为int映射给char，以此类推，循环直到字符串结束。
具体的代码如下，如果上面叙述的不清楚，可以看代码中我标注的注释。

class Solution2{
public:
	int lengthOfLongestSubstring(string s)
	{
		int sSize=(int)s.size();
		int start=0,end=0,length=0,result=0;
		unordered_map<char,int> hash;//建立从单个字符char->int索引的映射
		while(end<sSize)
		{
			char temple = s[end];
			if(hash.find(temple)!=hash.end() && hash[temple]>=start)
			//如果当前字符temple与其索引的映射关系已经在哈希表中并且该int索引
			//在起始位置之后，说明当前字符与哈希表中的一个字符重复
			{
				start = hash[temple] + 1;//1.将start修改为哈希表中已存在的重复字符的后一个字符
				length = end-start;//2.长度重算
			}
			hash[temple]=end;//将当前temple的字符在字符串中的索引映射给该字符

			++end;
			++length;
			result=max(result,length);
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解法3：桶优化

说桶优化难免晦涩，其实就是一个数组。
方法简单，直接上代码了。

//solution3:利用字符在ASCII表中对应的数字，做一个Vector，
//下标为对应的ASCII码值，里面存的内容为字符在字符串中的索引
//即vector索引为97对应字符'a'，索引98对应'b'
class Solution3{
public:
	int lengthOfLongestSubstring(string s)
	{
		int start(0), end(0), length(0), result(0);
		int sSize = int(s.size());
		vector<int> vec(128, -1);//用128数组记录ASCII中'a'~'Z'，并将值初始化为-1
		while (end < sSize)//字符串长度范围内循环
		{
			char tmpChar = s[end];
			//仅当s[start,end) 中存在s[end]时更新start
			if (vec[int(tmpChar)] >= start)
			//int(tmpChar)是将字符类型转换为对应的ASCII码,即容器的索引
			{
				start = vec[int(tmpChar)] + 1;
				length = end - start;
			}
			vec[int(tmpChar)] = end;//将字符在字符串中的位置索引赋值到
			//该字符ASCII对应的容器中，即通过一个数组来记录字符是否出现过

			end++;
			length++;
			result = max(result, length);
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Ps：现在自己刷题还是有些难度，相信研究一下大佬的思路慢慢积累经验就会好起来的。
PPs：有错误或者有什么更好的想法，欢迎各位大佬批评指正或给我建议促进我成长哦，蟹蟹！