LeetCode-3.无重复字符的最长字串

　　给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

　　示例 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 次遍历：以此类推

 import java.util.HashMap;

 class Solution {

     public int lengthOfLongestSubstring(String s) {

         //建立hashmap，记载每个字符出现的位置

         HashMap<Character,Integer> map=new HashMap<>();

         //记载起始的下标

         int index=0;

         int maxlen=Integer.MIN_VALUE;

         if(s.length()==0)

             return 0;

         //遍历字符串

         for(int i=0;i<s.length();i++){

             //得到下标为i的字符

             char c=s.charAt(i);

             //情况2

             if(map.containsKey(c)&&map.get(c)>=index){

                 //此时子串长度与maxlen比较，更新maxlen

                 maxlen=(i-index)>maxlen?i-index:maxlen;

                 //使index=重复字符下标+1，避开重复字符

                 index=map.get(c)+1;

             }

             //更新map

             map.put(c,i);

         }

         //最后再比较一次，以防止"abcdefg"该情况出现

         maxlen=(s.length()-index)>maxlen?s.length()-index:maxlen;

         return maxlen;

     }

 }

巴特西

LeetCode-3.无重复字符的最长字串

最新文章

热门文章