Longest Substring Without Repeating Characters题目及解法

问题描述：

Given a string, find the length of the longest substring without repeating characters.

示例：

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

问题分析：

题目主要是要求一个字符串中最长的连续子序列，序列中没有重复的字符。

1.先讲一下我的朴素思想：

主要是通过循环遍历，将最长的字符串取出，具体过程可以参考我的代码

class Solution {public:    int lengthOfLongestSubstring(string s){			map<char,bool> cmap;			int maxLen = 0;			int len = 1;			for(int i = 0; i < s.length(); i++){				initMap(cmap);				cmap[s[i]] = true;				for(int j = i+1; j < s.length(); j++){					if (cmap[s[j]]){						len = j - i;						break;					}					cmap[s[j]] = true;						len = j - i + 1;				}				if(len > maxLen){					maxLen = len;				}			}			return maxLen;		}				void initMap(map<char,bool>& cmap){			cmap.clear();			for(int i = 0; i < 26; i++){				cmap[(char)('a' + i)] = false;			}		}};当然，这种方式并不高效，时间复杂度是O（N^2）。
2.下面我们再看另一种分析：
举个例子string = “abcdefbc”来说，当我们顺序查找时，会发现指到第二个字符‘b’的时候，字符串最长子序列是“abcdef”。我们会发现，寻找下个最长子序列需要从第一个‘b’之后开始，也就是起始位置是字符‘c’，依次类推，可在线性时间内完成最长子串的查找。
我们看一下大神写的代码，一起来学习下思路：
int lengthOfLongestSubstring(string s) {        vector<int> dict(256, -1);        int maxLen = 0, start = -1;        for (int i = 0; i != s.length(); i++) {            if (dict[s[i]] > start)                start = dict[s[i]];            dict[s[i]] = i;            maxLen = max(maxLen, i - start);        }        return maxLen;    }是不是很简洁呢？哈哈哈，关键这个代码效率还比较高呢~~，如果有小伙伴有看不懂的地方，欢迎和我交流~~