无重复字符的最长子串-力扣3-java

一、题目描述

给定一个字符串 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;//当前最大子串长度，当前子串长度，当前子串左端下标Map<Character, Integer> map = new HashMap<>(); //保存当前子串每个字符对应的下标for(int i=0; i<len; i++){char c = s.charAt(i);if(!map.containsKey(c)){  //当前子串不包含该字符curlen++;ans = curlen>ans? curlen : ans;  //更新最大长度map.put(c, i);  //将当前字符加入到map中}else { //当前子串包含该字符int index = map.get(c);  //上次出现该字符的位置for(int j=lIndex; j<index; j++){//删除从子串最左端到上次出现该字符间的所有字符map.remove(s.charAt(j));}lIndex = index + 1;  //更新当前子串最左侧的下标curlen = i - index;  //重新计算当前子串长度map.put(c, i);  //更新当前字符在子串中的位置}}return ans;}
}