网站建设云平台,网络架构是什么意思,专业的国内网站建设公司,酷炫个人特别网站一、题目描述给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。示例 2:输入: s bbbbb输出: 1解释: 因为…一、题目描述给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:输入: s bbbbb输出: 1解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:输入: s pwwkew输出: 3解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。来源力扣LeetCode链接https://leetcode.cn/problems/longest-substring-without-repeating-characters著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。二、运行结果三、解题思路类似于使用滑动窗口设置一个哈希表保存当前子串的每个字符及其在原字符串中的下标并保存当前子串最左端下标,遍历字符串的每个字符做如下处理1如果在哈希表中不包含该字符表示当前子串没有出现过该字符则将当前子串的长度加1并更新当前最大子串长度如果需要更新的话将当前字符及其下标加入到哈希表中2如果哈希表中包含该字符表示当前子串已经出现过该字符则将当前子串总最左端开始到上次出现该字符中间的的所有字符从哈希表中删除将当前子串的最左端下标设置为上次出现该字符的下一个位置并重新计算当前子串的长度将哈希表中当前字符对应的下标设置为最新的下标直至遍历完字符串。注意只有在当前子串不包含当前字符时才需要更新最大长度如果子串中已经出现过当前字符则最大子串长度不用更新因为这时长度不会增加。四、AC代码class Solution {public int lengthOfLongestSubstring(String s) {int len s.length();int ans 0, curlen 0, lIndex 0;//当前最大子串长度当前子串长度当前子串左端下标MapCharacter, Integer map new HashMap(); //保存当前子串每个字符对应的下标for(int i0; ilen; i){char c s.charAt(i);if(!map.containsKey(c)){ //当前子串不包含该字符curlen;ans curlenans? curlen : ans; //更新最大长度map.put(c, i); //将当前字符加入到map中}else { //当前子串包含该字符int index map.get(c); //上次出现该字符的位置for(int jlIndex; jindex; j){//删除从子串最左端到上次出现该字符间的所有字符map.remove(s.charAt(j));}lIndex index 1; //更新当前子串最左侧的下标curlen i - index; //重新计算当前子串长度map.put(c, i); //更新当前字符在子串中的位置}}return ans;}
}
