字符串中双指针

1、最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从’a’到’z’的字符。

思路：前后指针分别指向不重复的最前和最后，后指针每次后移时，更新前指针：

map保存的是字符对应的位置；

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        int n = s.size();
        map<char,int> mp;
        int begin = 0,end = 0;
        int res = 0;
        while(end < n){
            //cout << end << s[end];
            if(mp.count(s[end])){
                //注意，begin不能回退
                begin = max(begin,mp[s[end]]+1);
                mp[s[end]] = end;
            }
            else mp[s[end]] = end;
            //cout << " " << begin << endl;
            res = max(res,end - begin + 1);
            end++;
        }
        return res;
    }
};

或者统计次数也可以：

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char,int> hash;
        int res = 0;
        for (int i = 0, j = 0; j < s.size(); j ++ )
        {
            //出现重复
            if ( ++ hash[s[j]] > 1)
            {   //i往后移，同时清零
                while (i < j)
                {
                    hash[s[i]]--;
                    i ++ ;
                    //找到重复的数
                    if (hash[s[j]] == 1) break;
                }
            }
            res = max(res, j - i + 1);
        }
        return res;
    }
};