题目如下：
Given a string, find the length of thelongest substringwithout repeating characters.
Examples:
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 asubstring,"pwke"is asubsequenceand not a substring.
分析题目：
首先区分一个概念： substring与subsequence，简而言之：subsequence可以不是原字符串中连贯的字符（可以略过某些字符），substring必须是原字符串中的一部分
好，下面来看一下题目：
这道题我认为关键在于遇到重复的时候，左面的起始计数位置怎么跳到之后对应的位置，这么说比较抽象，就是从直观上出发，我们在左边有个记录位置的int型 名为left，i 就是遍历变量， left起始为0[string第一个字母下标]，所以遇到的重复情况就是下面几种，上图：
由于遇到相同字母，此轮计数结束，接下来我们要决定left下一步往哪里跳，以便于进行下一轮计长度，如图：
综上我们可以看出，left的位置取决于重复字母出现的位置，这时我们就需要一个数组去记录字母出现的位置，在这里我使用的是vector<int> asc_table(256, -1)，由于ascii能表示256中字符，我为了left初始化可以与下标相配（即0），将所有字母初始位置设置为-1，再初始化asc_table[s[left]] = 0，之后就是asc_table[s[i]] = i。
由第二幅图可以看出，当 left <= asc_table[s[i]] 时，left = asc_table[s[i]] + 1，并且当前记录位置的asc_table[s[i]]被更新为最新的、更大一些的i，这样我们就可以进行下一轮长度计量。
这是这个思路写的代码：
class Solution {public: int lengthOfLongestSubstring(string s) { vector asc_table(256, -1);
int left = 0;
int length = 0;
int temp = 0;
asc_table[s[left]] = 0;
if (s.length() == 1) length = 1;
else
{
for (int i = 1; i < s.length(); i++)
{
if (asc_table[s[i]] == -1)
{
asc_table[s[i]] = i;
}
else
{
if (left <= asc_table[s[i]]) left = asc_table[s[i]] + 1;
asc_table[s[i]] = i;
}
temp = i - left + 1;
length = (length > temp) ? length : temp;
}
}
return length;
}
};
由于 asc_table[s[i]] = i 操作是共通的，所以我合并了一下代码为：
class Solution {public: int lengthOfLongestSubstring(string s) { vector asc_table(256, -1);
int left = 0;
int length = 0;
int temp = 0;
asc_table[s[left]] = 0;
if (s.length() == 1) length = 1;
else
{
for (int i = 1; i < s.length(); i++)
{
if (left <= asc_table[s[i]]) left = asc_table[s[i]] + 1;
asc_table[s[i]] = i;
temp = i - left + 1;
length = (length > temp) ? length : temp;
}
}
return length;
}
};
submit之后通过～这次效率可观，很开心！虽然写了很久～这就是今天的积累啦！
网友评论