leetcode面试经典150题——31 无重复字符的最长子串（方法二极简代码！！！）

本文介绍: 设定两个指针 left和right 指向最长子串的头部和尾部的下一个元素，left和right初始分别为0和1，对于rig h t 指向的每一个元素我们都在前面left和righ t 区间内寻找是否出现过，若未出现过，则把它加入子串中，，righ t 指针右移，若出现过，left 指针移动到出现的元素后一个位置，righ t 指针移动到出现的元素后两个位置，最后再更新最长子串的长度。时间复杂度：o（n）left，righ t 指针均只会向右移动，遍历一遍字符串，时间复杂度为o（n）空间复杂度：o（n）哈希表的空间为o（n）

描述：
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:

输入: s = “abc abc b b”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
leetcode链接

int lengthOfLongestSubstring(string s) {
	int n = s.size();
	if(n==1){//字符串只有一个元素，那么最长无重复子串长度也为1
		return 1;
	}
	int left = 0,right = 1;
	int maxLen = 0;
	while(right<n){
		int i = left;
		//在子串中查找相同的元素
		while(s[right]!=s[i]&amp;&amp;i<right){
			i++;
		}
		if(i==right){
		//没有相同的元素则加入子串中
			right++;
		}else{
			left = i+1;
			right = i+2;
		}
		//更新最大的子串长度
		maxLen = max(maxLen,right-left);
	}
	return maxLen; 
}

int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int left = 0,right = 0;
        int maxLen = 0;
        unordered_map<char,int> map;
        while(right<n){
            while(left<right&amp;&amp;map.count(s[right])){
                //删除有重复字符的子串直至不出现重复的字符
                map.erase(s[left++]);
            }
            //把right指向的元素当成关键字插入map
            map[s[right++]] = 0;
            maxLen = max(maxLen,right-left);
        }
        return maxLen;
    }