Longest Substring Without Repeating Characters，longestrepeating

Longest Substring Without Repeating Characters

一、题目说明

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

题目大概意思就是从一个字符串中找出一个最大的没有重复字母的子串，并且求出这个字串的长度

二、解题思路

解决方法大家都能想得到。我们用rear表示最大子串的起始位置，front表示最大子串的终止位置，刚开始时front ==rear==0。然后用了两个map容器，一个map容器用来保存字符访问记录，具体结构是：map《char,bool》，访问过为true，没有访问过为false。另外一个容器用来保存已经被访问过的字符所在的索引，准确的说是保存当前的最大子串中字符的索引，为map《char,int》，front每次向前挪动一个位置，检查该位置的字符是否已经在最大子串中出现。同时用tempLength表示新子串长度，maxLength表示最大子串长度先设这个字符为m

a 将rear到m所在位置索引间隔内的字符的访问记录全部设置为false，但是不更新字母m的访问记录，即其访问记录为true

b rear = m所在索引位置+1，tempLength = front - rear+1

c 更新m所在索引位置为当前的位置，即更新为当前的front值

三、代码

#include<map>
class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        map<char, unsigned> mapChrIndx; //字母对应的索引
    map<char, bool> mapVstRcrd;     //字母访问记录，true为访问过，false为没有访问过           
    int maxLength = 0;              //记录最大长度
    int tempLength = 0;             //临时记录的长度
    int front=0,rear = 0;           //当前最大字符串起始位置和终止位置
    std::size_t len = s.size();
    while (front < len&&rear<len)
    {
        //当前字符没有被访问过，最大长度+1，并且设置为访问，保存当前字符所在索引
        if (mapVstRcrd[s[front]] == false)
        {
            mapVstRcrd[s[front]] =true;
            mapChrIndx[s[front]] = front;
            ++tempLength;                       //临时长度+1
        }
        else
        {
            //将之前点的索引全部置为没有访问过，新的点从重复位置的下一个位置开始算起
            int endIndx = mapChrIndx[s[front]];     //获取该字母之前出现的索引
            for (rear; rear != endIndx; ++rear)
                mapVstRcrd[s[rear]] = false;
                    mapChrIndx[s[front]] = front;               //同时更新索引
            rear = endIndx + 1;
            tempLength = front - rear + 1;          //重新更新临时长度
        }
        if (tempLength > maxLength)                 //更新最大子串长度
            maxLength = tempLength;
        ++front;
    }
    return maxLength;
    }
};

四、时间复杂度分析

- 最外层一个循环复杂度为n，里面if-else语句，if语句的复杂度为logn，else复杂度为T*logn，T为子串长度，子串长度越长，即T越大，T*logn出现的次数越少， 因此大概将T视为一个常数，因此，总的复杂度为O(n*logn)