给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
题目思路：建立hashmap，记载每个字符出现的位置，并设变量index记载子串起始的下标，然后从下标为0开始遍历字符串
遍历到下标i时，此时有两种情况：
1.hashmap中没有该字符s.charAt(i)或者hashmap中有该字符s.charAt(i)，但该字符map.get()不在index后，此时可以直接map.put(),添加或替换数据
2.hasmap中有该字符s.charAt(i)并且map.get()在index后，此时代表有重复字符，计算此时的字串，并使index=重复字符下标+1，最后map.put()替换数据
详细说明例子： （i为遍历下标，char为s.charAt(i)，index为子串开始下标）
输入：“abcabcbb”
第一次遍历：i=0，char=a，进入情况1，index=0，子串：“a”，map中（a：0）
第二次遍历：i=1，char=b，进入情况1，index=0，子串：“ab”，map中（a：0，b：1）
第三次遍历：i=2，char=c，进入情况1，index=0，子串：“abc”，map中（a：0，b：1，c：2）
第四次遍历：i=3，char=a，进入情况2，因为map.get（a）=0>=index，所以有重复数据a，计算此时的子串长度（3-0=3），与最大长度比较，并让index+=1，更新map数据
index=1，子串：“bca”，map中（b：1，c：2，a：3）
第 i 次遍历：以此类推
1 import java.util.HashMap; 2 class Solution { 3 public int lengthOfLongestSubstring(String s) { 4 //建立hashmap，记载每个字符出现的位置 5 HashMap<Character,Integer> map=new HashMap<>(); 6 //记载起始的下标 7 int index=0; 8 int maxlen=Integer.MIN_VALUE; 9 if(s.length()==0) 10 return 0; 11 //遍历字符串 12 for(int i=0;i<s.length();i++){ 13 //得到下标为i的字符 14 char c=s.charAt(i); 15 //情况2 16 if(map.containsKey(c)&&map.get(c)>=index){ 17 //此时子串长度与maxlen比较，更新maxlen 18 maxlen=(i-index)>maxlen?i-index:maxlen; 19 //使index=重复字符下标+1，避开重复字符 20 index=map.get(c)+1; 21 } 22 //更新map 23 map.put(c,i); 24 } 25 //最后再比较一次，以防止"abcdefg"该情况出现 26 maxlen=(s.length()-index)>maxlen?s.length()-index:maxlen; 27 return maxlen; 28 } 29 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
