舞蹈东莞网站建设,wordpress获取最新发布列表,做外贸大大小小的网站有哪些,杭州网络有限公司力扣 3 无重复字符的最长字串
题目描述
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。示例 2:
输入: s…力扣 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 * 104s 由英文字母、数字、符号和空格组成
思路分析
关于这道题用滑动窗口的思想来做的话会非常麻烦既要考虑最长的字串长度同时还要保证不出现重复字符考虑窗口里的每一个字符不重复我们可以用一个非常巧妙的思路
这个思路利用了关于哈希算法以及字符的ascii编码来进行。我们首先定义一个数组名为hash容量为256的数组初始化为0。随后开始遍历整个字符串这里需要两层循环利用每一个字符的ascii编码当作数组的下标如果下标对应的值为零我们设置为1并进入下面if语句的运行如果下一个字符和它相等就不会进入接下来的判断这是判断不出现重复字符的方法。
关于求最长的字串长度我们利用两个下标从第一个字符开始如果接下来的字符对应的下标的数组为0就进入if语句此时遍历的两个下标的差值在加上原来的第一个字符也算不重复的字串便是不出现重复字符字串的长度同时定义一个max值保留每一次的最大值即可。
完整代码
int lengthOfLongestSubstring(char* s) {int j0;int i0;int max1;int nstrlen(s);if(n0){return 0;}for(i0;in;i){int hash[256]{0};for(ji;jn;j){if(hash[s[j]]0){hash[s[j]]1;if(j-i1max){maxj-i1;}}else{break;}}}return max;}
