丰县徐州网站开发,怎么查网站备案接入商,湖州住房和城乡建设局网站,济南广运建设公司网站题目描述#xff1a;
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。示例 2:
输入: s bbbbb
给定一个字符串 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 left0,right0;int len0,max0;int hash[256]{0};for(;s[right]!\0;right){if(hash[s[right]]!0hash[s[right]]left){lefthash[s[right]];}hash[s[right]]right1;lenright-left1;if(lenmax) maxlen;}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或者在循环前定义nstrlen(s);不要偷懒直接把for循环判定写成rightstrlen(s)这样每次for循环都要调用一遍时间复杂度为n的strlen函数增加了很多不必要的时间开销。csapp后遗症,dddd
