网站cms建设,大沥网站建设公司,镇江网站建设费用,阿里指数查询手机版题目
给定一个字符串 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 是一个子序列不是子串。示例 4:
输入: s
输出: 0提示
0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
哈希表的实现
在遍历字符串的同时使用HashMap记录将字符与字符出现的下标当遍历到不存在哈希表中的字符时说明该字符不是一个重复的可以记录在当前长度。如果出现在当前哈希表中说明是个重复字符下一次记录长度应该在该字符的下一个位置进行重新记录。 具体实现代码如下 class Solution {public int lengthOfLongestSubstring(String s) {if(s.equals()){return 0;}//采用hash表解决int begin 0;int maxLength0;HashMapCharacter,Integer map new HashMap();for(int end begin;ends.length();end){char ch s.charAt(end);if(map.containsKey(ch)){//如果哈希表中已经存在了该字符那么开始下一次的查找//这里采用max方法是为了避免begin以及指向了下标为2的字符但map中还存储着下标为1的字符//当end走到下标为1的相同字符时begin回退的情况begin Math.max(map.get(ch)1,begin);map.put(ch,end);}else{//如果不存在那么将该字符存放在哈希表中。map.put(ch,end);}maxLength Math.max(maxLength,end-begin);}return maxLength1;}
}
数组的实现
因为题目说到了字符串中只包含英文、空格、符号与数字总共加起来只有128个字符因此我们可以采用数组来实现数组长度为128不同的字符ascii码值作为下标字符上一次出现的位置作为数组中存储的值。 具体实现代码如下。 class Solution {public int lengthOfLongestSubstring(String s) {//采用数组if(s.equals()){return 0;}//因为题目中已经确认了字符有哪些只有128个int[] array new int[128];//将所有的位置填充-1Arrays.fill(array,-1);int begin 0;int maxLength0;for(int end 0;ends.length();end){char ch s.charAt(end);if(array[ch]!-1){//说明该字符以及出现过了begin Math.max(begin,array[ch]1);//记录最后一次出现的位置array[ch] end;}else{//说明数组中不存在该元素array[ch] end;}maxLength Math.max(maxLength,end-begin);}return maxLength1;}
}
