免费自助建站网站一览阿里云 企业 网站

题目描述：

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

示例 1:

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

示例 2:

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

示例 3:

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

我的解法：

int lengthOfLongestSubstring(char* s) {int left=0,right=0;int len=0,max=0;int hash[256]={0};for(;s[right]!='\0';right++){if(hash[s[right]]!=0&&hash[s[right]]>left){left=hash[s[right]];}hash[s[right]]=right+1;len=right-left+1;if(len>max) max=len;}return max;
}

        分析：由于题目没有限定空间，可以开一个数组，用ASCII码实现哈希映射。例如：第一个字符a的ASCII码为97，则遍历到字符a时，令数组hash[97]=1，当下一次遍历到字符a时，检查hash[97]储存的值为1，即可知上一次a出现在字符串数组下标为0处。（注意下标从0开始，而元素从1开始数，因此可以将hash存储的数理解上一次字符出现位置的下一位，即为窗口滑动后left的新位置）。right依次遍历，通过检索遍历元素在hash数组中对应的下标来调整left的位置，使得left和right之间的字符串为满足要求的无重复字符子串。插一嘴，for循环判定时最好用s[right]!='\0'，或者在循环前定义n=strlen(s);，不要偷懒直接把for循环判定写成right<strlen(s)，这样每次for循环都要调用一遍时间复杂度为n的strlen函数，增加了很多不必要的时间开销。（csapp后遗症,dddd）