剑指offer. 最长不含重复字符子串
注意该题与leetcode第3题类似，但是leetcode的字符范围更广，不只是限制在a-z
数据范围
输入字符串长度 [0,1000]。
样例
输入：“abcabc”
输出：3
01方法一 双指针
使用两个首尾指针start，end。如果end指针遇到前面已经存在的字符就需要移动start指针，直到子字符串中没有重复字符串。实现方法有多种，可以采用遍历查找的方法，判断从start到end是否有重复字符，也可以采用哈希的方式存储已经遍历过的字符串，也可以采用数组的方式存放已经遍历的方式，根据具体情况使用，这种题型下采用哈希会得不偿失，因为使用哈希还是数组本质在于快速查找目标元素的索引下表，本题用的是字符，所以可以使用ASCII字符的decimal值作为数组的索引，如果索引没办法直接得到，可以使用哈希的方式。
class Solution{
public:int longestSubstringWithoutDuplication(string s) {int startIndex=0,endIndex=0;int currentLength=0, maxLength=0;for(int i=0;i<s.size();i++){char pendchar = s[i];for(int j=startIndex;j<endIndex;j++){if(pendchar == s[j];startIndex = j+1;currentLength = endIndex-startIndex;}endIndex++;currentLength++;maxLength = max(maxLength, currentLength);}return maxLength;}};02双指针+数组
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {int startIndex=0,endIndex=0;int currentLength=0, maxLength=0;vector<int> arr(128,-1);// map<char, int> charmap;//abca chbmmcgfor(int i=0;i<s.size();i++){char pendchar = s[i];if(arr[pendchar]>=startIndex){startIndex = arr[pendchar]+1;currentLength = endIndex-startIndex;}arr[pendchar] = i; endIndex++;currentLength++;maxLength = max(maxLength, currentLength);}return maxLength;}};
03双数组＋map
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {int startIndex=0,endIndex=0;int currentLength=0, maxLength=0;map<char, int> charmap;//abca chbmmcgfor(int i=0;i<s.size();i++){char pendchar = s[i];auto it = charmap.find(pendchar);if(it!=charmap.cend()&&it->second>=startIndex){startIndex = it->second+1;currentLength = endIndex-startIndex;}charmap[pendchar] = i; endIndex++;currentLength++;maxLength = max(maxLength, currentLength);}return maxLength;}
};
使用map时一定要注意什么时候，才能更新startIndex，比如遇到字符串“chbmmcg”，在遇到m重复时，此时startIndex已经移动到第二个m的位置4，但是之后遇到c，在map中也是存在的，但是此时不能进入更新startIndex，所以要加限制条件当前重复元素的索引必须大于startIndex.
04双指针＋set
class Solution {
public:int lengthOfLongestSubstring(string s) {std::unordered_set<char> charset;int ans=0, left = 0;for(int i=0;i<s.length();i++){while(charset.find(s[i])!=charset.end()){charset.erase(s[left]);++left;}charset.insert(s[i]);ans = std::max(ans, i-left+1);}return ans;}
};
下面也这道题也是需要注意，使用while循环要将在set中重复的元素删到为止，举例“pwwkew”，在遇到第二个w时，移动left指针，此时第一个w还是在子串中。
