LeetCode 第三题（C语言）

Dear 丶 2022-05-03 11:30 258阅读 0赞

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例 1:

输入: “abcabcbb”  
输出: 3  
解释: 无重复字符的最长子串是 “abc”，其长度为 3。  
示例 2:

输入: “bbbbb”  
输出: 1  
解释: 无重复字符的最长子串是 “b”，其长度为 1。  
示例 3:

输入: “pwwkew”  
输出: 3  
解释: 无重复字符的最长子串是 “wke”，其长度为 3。  
请注意，答案必须是一个子串，“pwke” 是一个子序列 而不是子串。

--------------------

1.  暴力求解法

//判断是否唯一
    	int IsUnique(char *s, int i, int j)
    	{ 
    		for (int k = i; k < j; k++)
    		{ 
    			if (s[j] == s[k]) return 0;
    		}
    		return 1;
    	}
    	
    	int lengthOfLongestSubstring(char* s) { 
    		int length = strlen(s);
    		int max = 0;
    		for (int i = 0; i < length; i++)
    		{ 
    			for (int j = i + 1; j <= length; j++)
    			{ 
    				if (IsUnique(s, i, j))
    				{ 
    					max = (j - i) > max ? (j - i) : max;
    				}
    				else
    				{ 
    					max = (j - i) > max ? (j - i) : max;
    					break;
    				}
    			}
    		}
    		return max;
    	}

**但这个算法的时间复杂度为0(n^3)。**

1.  运用哈希表  
    使用两个快慢指针，快的为start，慢的为i。

*  快指针走，只要哈希表中没有该元素，就一直走并及时更新max，直到出现重复的
 *  先把慢指针在哈希表中位置清0，慢指针走一步
 *  重复上面两步，直到快指针走到结束

int lengthOfLongestSubstring(char* s)
    	{ 
    		int Hash[128] = {  0 }; //因为不知道字符串李哪种符号（有可能不是字母），ASCII使用128
    		int max = 0;
    		int start = 0;
    		int i = 0;
    		int length = strlen(s);
    		while (i < length && start < length)
    		{ 
    			if (Hash[s[start]] == 0) { 
    				Hash[s[start]] = 1;
    				start++;
    				max = (start - i) > max ? (start - i) : max;
    			}
    			else { 
    				Hash[s[i]] = 0;
    				i++;
    			}
    		}
    		return max;
    	}

这个算法的时间复杂度O(n)。