网站建设公司广州东营网站建设

力扣 3 无重复字符的最长字串

题目描述

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

思路分析

关于这道题用滑动窗口的思想来做的话会非常麻烦，既要考虑最长的字串长度，同时还要保证不出现重复字符（考虑窗口里的每一个字符不重复），我们可以用一个非常巧妙的思路

这个思路利用了关于哈希算法以及字符的ascii编码来进行。我们首先定义一个数组名为hash，容量为256的数组，初始化为0。随后开始遍历整个字符串，这里需要两层循环，利用每一个字符的ascii编码当作数组的下标，如果下标对应的值为零，我们设置为1，并进入下面if语句的运行，如果下一个字符和它相等，就不会进入接下来的判断，这是判断不出现重复字符的方法。

关于求最长的字串长度，我们利用两个下标，从第一个字符开始，如果接下来的字符对应的下标的数组为0就进入if语句，此时遍历的两个下标的差值在加上原来的第一个字符（也算不重复的字串）便是不出现重复字符字串的长度，同时定义一个max值保留每一次的最大值即可。

完整代码

int lengthOfLongestSubstring(char* s) {int j=0;int i=0;int max=1;int n=strlen(s);if(n==0){return 0;}for(i=0;i<n;i++){int hash[256]={0};for(j=i;j<n;j++){if(hash[s[j]]==0){hash[s[j]]=1;if(j-i+1>max){max=j-i+1;}}else{break;}}}return max;}