LeetCode Longest Substring Without Repeating Characters

LeetCode 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.


本题要求找出字符串中没有重复字母的最长连续子串。最快想到的是两重遍历i,j,每次用set判断是否重复,重复就进行下一次遍历i++,但是这样显然超时。

因为字符串中只有ASCII,所以可以用bool hash[128]来判断是否有重复字符,比set要快(用空间换时间)。

另外,假设遍历状态是abcdefgc,发现有两个'c',下一次遍历的时候没必要从b开始遍历,因为从b开始肯定也会遇到后面的两个'c',但此时字符串长度比之前的少1,所以可以直接从上次的'c'的下一个字母'd'开始重新遍历,这样可以节省不少时间。

完整代码如下:

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int longest = 0, n = s.size(), cur = 0;
		vector<int> hash(128, 0);
		for (int i = 0; i < n; i++)
		{
			if (hash[s[i]])
			{
				if (cur > longest)
					longest = cur;
				cur = 0;
				i = hash[s[i]];//从重复字符下一个字符开始遍历
				//memset(&hash[0], 0, 128*sizeof(int));//比fill更快,但是没fill安全
				fill(hash.begin(), hash.end(), 0);
			}
			hash[s[i]] = i + 1;//记录下一个字符下标
			cur++;
		}
		return (longest > cur) ? longest : cur;
	}
};

本代码提交AC,用时68MS。

二刷,上面我的解法太过复杂。其实我们可以用一个map保存出现字符的最大下标,start保存一个下标,使得从start到当前字符这个区间不存在重复字符。

每来一个字符,我们去map中找一下,如果该字符之前存在,则更新start为最大下标(为了满足从start到当前字符这个区间不存在重复字符),然后不重复子串的长度就是i-start。

完整代码如下,因为s只包含字符,所以也可以用一个256长的数组表示map。

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		map<char, int> visited;
		int ans = 0, start = -1;
		for (int i = 0; i < s.size(); ++i) {
			if (visited.find(s[i]) != visited.end())
				start = max(start, visited[s[i]]);
			visited[s[i]] = i;
			ans = max(ans, i - start);
		}
		return ans;
	}
};

本代码提交AC,用时22MS。

Leave a Reply

Your email address will not be published. Required fields are marked *