【LeetCode】3. Longest Substring Without Repeating Characters的两种解法，leetcoderepeating

【LeetCode】3. Longest Substring Without Repeating Characters的两种解法，leetcoderepeating

3. Longest Substring Without Repeating Characters

Total Accepted: 140752 Total Submissions: 644939 Difficulty: Medium

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

【分析】

     1.如题所言，寻找给定字符串的无重复字符最大子串，因此，首先明确一点，遍历整个字符串不可避免；

     2.涉及子串的长度，必然需要记录子串的首尾下标，首尾下标用High、Low标记，当当前字符与前面无重复时，High前移；当当前字符与前面出现重复时，首先计算当下子串长度MaxLen=High-Low；Low移动至子串中重复字符的下标的前一个位置，并且将这一段被截去的字符全部重新设置为未出现过的标记。

     3.对于确定字符是否出现过或者字符出现次数统计，一种有效的方法是哈希表，将字符ASCII值转化为哈希表键值，如此，查找的时间复杂度仅为O(1)；

【解法一】

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
     {
         if(s.size()==0)return 0;
         unsigned int Head,Tail,MaxLen;
         int position[256]={0};//分别记录256个字符第一次出现在字符串中的位置（哈希表）
         vector<bool> repeat(256,0);//分别标记256个字符是否出现过(哈希表)
         Head=Tail=MaxLen=0;//子串首尾，最大子串长度
         for(int i=0;i<s.size();i++)//遍历字符串
         {
             if(repeat[s.at(i)]==0)//查询字符串中第i个字符是否出现过，未出现过，则此次为第一次出现，标记
             {
                  position[s.at(i)]=i;//记录字符第一次出现在原字符串中的下标
                  repeat[s.at(i)]=1;//标记出现
                  Tail++;//子串尾端+1
                  if(MaxLen<Tail-Head)//计算子串长度
                     MaxLen=Tail-Head;
             }
            else//第i个字符已经出现过（查阅哈希表，标记量为1）
             {
                for(int j=Head;j<position[s.at(i)];j++)//首端被截去，则在现有字串中视为未出现，对应哈希表标记量置零）
                    repeat[s.at(j)]=0;
                    Head=position[s.at(i)]+1;//更新首端下标
                    position[s.at(i)]=i;//记录第i个字符第一次出现的位置
                    Tail++;//尾端前移
                    if(MaxLen<Tail-Head)//最大子串
                    MaxLen=Tail-Head;
             }
         }
         return MaxLen;
    }
};

【解法二】

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int Length= s.length();
        int Low= 0, High= 0;
        int maxLen = 0;
        bool exist[256] = { false };
        while (High< Length) 
        {
           if (exist[s[High]]) 
           {
                maxLen = max(maxLen, High-Low);
                while (s[Low]!= s[High]) 
                {
                   exist[s[Low]] = false;
                   Low++;
                }
                Low++;
                High++; 
           } 
           else
           {
                exist[s[High] = true;
                High++;
           }
        }
        maxLen = max(maxLen, Length-Low);
        return maxLen;
    }
};