首页 > 代码库 > 【leetcode】 Longest Substring Without Repeating Characters

【leetcode】 Longest Substring Without Repeating Characters

2024-07-06 17:09:57   228人阅读

题目：

给定一个字符串，返回该串没有重复字符的最长子串。

分析：

1）子串：子串要求是连续的。
2）无重复，出现重复就断了，必须从新的位置开始。而新的位置就是重复字符第一次出现位置的下一个位置。
3）整个串可能没有一处重复。

那么，为了找出当前访问的字符是否出现过，要怎么做呢？当然是hash，O(1)的时间，而且既然是字符， 定义个255的hash table 就可以了，hash table 中的元素为相应字符在s中出现的位置。初始化为-1，表示都没有出现。
我们另外定义一个start 和end变量，来记录当前不重复子串的起始点，再定义一个记录最长子串的max_len变量，当当前不重复子串的长度大于最大值时，更改其值。

看个例子：

初始时 start = end = 0，随着end的移动，将遇到的字符的index加入到hash table 中，直到end = 3 的时候，发现 hash[ s[ end ] ] != -1,说明字符 b 在前面出现了，也就是说出现了重复，那么此时我们记录当前不重复的子串的长度 = end - start = 3 ， 也就是abc子串。将该值3与max_len进行比较，更新max_len 的值。
那么此时start 的值应该怎么更新是最终要的，图中我们将其更改为2，这是怎么得来的呢？因为子串要求是连续的，当end = 3出现重复时，说明从 0 开始的s最长无重复子串的长度就是 3，因为不允许跳过这个重复的b继续向后进行，所以，更长的子串肯定只能出现在第一个b字符的后一个字符为起始点的情况。
hash table的处理是将新 start前的元素清除，即改为 -1 ，同时保存从新start 到end间的信息。这样end 走到最后就完成了。

实现：

int lengthOfLongestSubstring(string s) {
	int len = s.size();
	if(len <= 1)
		return len;
	//hash_table,record the index of items in s
	int hash_table[255];
	//-1 means haven't occur  
	memset(hash_table, -1, sizeof(hash_table));

	int start = 0;
	int end = 0;
	int max_len = 0;
	while(end < len)
	{
		char c = s[end];
		if(hash_table[c] == -1)
				hash_table[c] = end++;
		else
		{
			max_len = max(max_len, end - start);
			//new start
			start = hash_table[c] + 1;
			//clean items in hash_table .
			memset(hash_table, -1, sizeof(hash_table));
			//record the index of items from new start to end.
			for(int i = start; i <= end; ++i)
				hash_table[s[i]] = i;
			++end;
		}
	}
	//may be the s without repeating character from start to end.
	max_len = max(max_len, end - start);
	return max_len;
}


联系
我们