Given a string, find the length of the longest substring without 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 a substring, “pwke” is a subsequence and not a substring.
原题：https://leetcode.com/PRoblems/longest-substring-without-repeating-characters/?tab=Description
分析： 题意应该已经默认了所有出现的字符均为ASCII字符集内。于是可以创建一个256个int型数的数组int dict[256]，用于记录每一个字符最后一次出现的位置i, i ∈ [ 0, s.size() )，其中s为给定的字符串。定义maxLen为字串的最大长度，start为最大字串的下限，i为迭代数同时也最为最大字串的上限，最大字串范围：( start, i ]。算法执行过程： 首先，start默认为-1，dict[256]初始化为-1，maxLen初始化为0。 其次，开始迭代过程，将字符串s从头到尾读一遍。如果发现有重复读到的字符，则将start提升至该重复字符的第一个字符位置处。然后，不论上述条件是否成立，均将当前字符的最新位置存储到dict[]中。最后计算当前无重复的字串是否比现有maxLen要大，如果是，则将maxLen的值替换为当前无重复字串的长度。以上步骤能得出正确结果，是因为它首先使用了当前字符s[i]在上一次出现的位置，( 即dict[ s[i] ]的值，如果dict[ s[i] ] != -1，则表明该字符s[i]出现过，是一个重复的字符，其次判断s[i] > start，如果条件成立，则判断重复字符位于当前定义的最长字串内，从而要更新当前定义的最长字串，方法是执行start = dict[ s[i] ]，) 然后再将当前s[i]的位置i覆盖到dict[ s[i] ]中。 以下是代码：class Solution {public: int lengthOfLongestSubstring(string s) { vector<int> dict(256, -1); int maxLen = 0, start = -1; for (int i = 0; i != s.length(); i++) { if (dict[s[i]] > start) start = dict[s[i]]; dict[s[i]] = i; maxLen = max(maxLen, i - start); } return maxLen; }};注：这个算法引用自： https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Solutions （2.C++ code in 9 lines.）
新闻热点
疑难解答
