[C++知识库]无重复字符的最长子串(C语言)

题目：给定一个字符串p，请你找出其中不含有重复字符的最长子串的长度。

1 暴力求解

对一个任意的字符串，要找到它的最长子串，我们很容易会想到遍历每一个子串。下面一段代码会遍历每一个子串，对于其中的某一个子串，我们还需要判断它是否满足无重复字符。

在这里字符串长度为len，其所有非空子串的个数为len!(阶乘)个，而每一次判断是否无重复字符的时间复杂度为O(n2)，所以这种算法非常慢。当字符串长度非常长时，基本得不到结果。

#include <stdio.h>
#include <string.h>
int main(){
	int len, output=0, i, j, k, m, sub_status=1;
	char p[] = "aaabc";
	len = strlen(p);
	for(i=0;i<len+1;i++){
		for(j=0;j<len-i+1;j++){
			sub_status=1;
			for(k=j;k<j+i-1;k++){
				for(m=k+1;m<j+i;m++){
					if(*(p+k)==*(p+m)){
						sub_status=0;
						break;
					}		
				}
				if(sub_status==0)continue;
			}
			if(sub_status==1){
				output=i;
				break;
			}
		}
	}
	printf("%d", output);
}

2 更好方法

子串中的字符在原字符串中是连续出现的，这个特点可以让我们减少“暴力解法”中判断是否有重复字符的开销。我们可以将元素一个个地放入队列中，放入新元素后，我们判断原队列中是否有重复的字符。如果有，那么将这个重复字符以及前面所有的字符丢弃，得到一个新的队列，这样可以始终保持队列中没有重复元素。在这个过程中，每一个得到的新队列都是一个无重复字符的子串，我们只需比较他们的长度并选出最长的一个。

#include <stdio.h>
#include <string.h>
int main(){
	int len, output=0, i, j, head=0, tmp;
	char p[] = "jfdksliwi";
	len = strlen(p);
	for(i=1;i<len;i++){
		for(j=head;j<i;j++){
			if(*(p+j)==*(p+i)){
				head=j+1;
				break;
			}
		}
		tmp = i+1-head;
		if(tmp>output)
			output = tmp;
	}
	if(len-head>output)
		output = len-head;	
	printf("%d", output);
}

leetcode提交代码：

int lengthOfLongestSubstring(char * s){
	int len, output=0, i, j, head=0, tmp;
	len = strlen(s);
	for(i=1;i<len;i++){
		for(j=head;j<i;j++){
			if(*(s+j)==*(s+i)){
				head=j+1;
				break;
			}
		}
		tmp = i+1-head;
		if(tmp>output)
			output = tmp;
	}
	if(len-head>output)
		output = len-head;
    return output;
}