面试热题（无重复字符的最长子串）

小灰灰 2023-10-14 12:39 14阅读 0赞

### 无重复字符的最长子串 ###

> 给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。
> 
>     输入: s = "abcabcbb"
>     输出: 3 
>     解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解法一：

public int lengthOfLongestSubstring(String s) {
          if(s==null){
              return 0;
          }
          int max=0;
          //因为s中包含数字、英文、符号，所以设置长度为128
          int[] hash=new int[128];
          //右指针
          int right=0;
          //左指针
          int left=0;
          //while条件right<s.length()
          while(right<s.length()){
                int c=s.charAt(right++);
                //hash数组对应的位置+1
                hash[c]++;
                //说明left~right+1中有重复字符
                while(hash[c]>1){
                    hash[s.charAt(left++)]--;
                }
              max=Math.max(max,right-left);
          }
          return max;
        }

![d37f3204493b439384503a425c4383d2.png][]

*  对入参进行判断，排除一些不合法的条件
 *  设置同向指针，left、right(相当于是两个前后指针)
 *  right不断的向后走，记录中途的字符，用hash表进行统计，如果统计时发现hash\[i\]>1,就说明当前字符在之前已经出现过
 *  left向后走，找到重复的元素位置上，然后移动到重复字符第一次出现的索引index +1的位置上，这时候计算max的值（最大长度）

解法二：

public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int left=0;
            int max=0;
            //将字符串转换为char
            char[] str=s.toCharArray();
            int[] hash=new int[128];
            for(int right=0;right<s.length();right++){
                char c=str[right];
                hash[c]++;
                while(hash[c]>1){
                    hash[str[left++]]--;
                }
                int val=right-left+1;
                max=Math.max(val,max);
            }
            return max;
        }

大体过程如上题所示

解法三：

public int lengthOfLongestSubstring(String s) {
                 //创建一个map数组，值对应键值，然后两个索引，加一个最大值的子串长度
            //入参进行判断
            if(s.length()==0){
                return 0;
            }
            //创建一个map数组用于存放输出的单个字符-索引
            Map<Character, Integer> arr=new HashMap<>();
            //定义两个指针
            int i=0;
            int j=0;
            //定义最大的长度变量
            int max=0;
            //对字符串进行循环遍历
            for ( i = 0; i <s.length() ; i++) {
                //将对应索引的字符赋给变量key
                char key=s.charAt(i);
                //输出一个字符之后要和map中的数组进行比较，如果没有包含，直接加入到map数组中去，
                //如果有，则将j指针移到对应的i位置上去，再进行遍历
                if(arr.containsKey(key)){
                    j=Math.max(arr.get(key),j);
                }
                    //保存最大长度
                    max=Math.max(max,i-j+1);
                    //不断地往数组中加字符
                    arr.put(s.charAt(i),i+1);
                
            }
            return max;
        }

![7d0d483bce4f4893b665de9ae590aaaa.png][]

*  对入参进行判断
 *  创建一个hash表，记录索引的位置
 *  定义同向指针
 *  遍历右指针，收缩左指针
 *  每次遍历一个字符将字符添加到hash表中，并添加对应的索引
 *  输出一个字符之后和map中的key进行比较，如果没有包含，直接加到hash表中去
 *  如果有，则收缩左指针，再次进行遍历
 *  保存最大长度（左闭右闭）
 *  每次添加元素索引的时候添加对应元素的idnex+1,符合左闭的条件

这时候肯定有人想问我，为什么在计算这类长度的时候，有的时候是s=right-left,而有的时候是s=right-left+1呢？这得看你自己定义的是左闭右开还是左闭右闭，有些人每次的糊里糊涂的做题，过了就没有再仔细深究，其实这与你的循环有着莫大的关系，仔细的同学已经发现我第一种解法用的是right-left,可是第二种解法就是用的right-left+1,接下来给大家揭秘这种应该怎么去选择

第一种方法：

while(right<s.length()){
        int c=s.charAt(right++);
         ...
    }

假如我们right已经到达了s.length-1的位置上，是不是进来还得做一次right++的操作

![b389d05684d04c79ac4bb3bd6759c12f.png][]

由上图我们可以清楚的看到right取到了比我们s长度还要大的位置上，这种情况就是右开，所以长度就是right-left

第二种方法：

for(int right=0;right<s.length();right++){
                char c=str[right];
              
            }

假如我们right已经到达了s.length-1的位置上，进来也没有对right进行任何操作，所以最后right索引是停在b这个位置上

![49bb85d258c647b9a2168512418fff19.png][]

由上图我们可以清楚的看到right取到了比我们s长度还要大的位置上，这种情况就是右闭，所以长度就是right-left+1

[d37f3204493b439384503a425c4383d2.png]: https://img-blog.csdnimg.cn/d37f3204493b439384503a425c4383d2.png
[7d0d483bce4f4893b665de9ae590aaaa.png]: https://img-blog.csdnimg.cn/7d0d483bce4f4893b665de9ae590aaaa.png
[b389d05684d04c79ac4bb3bd6759c12f.png]: https://img-blog.csdnimg.cn/b389d05684d04c79ac4bb3bd6759c12f.png
[49bb85d258c647b9a2168512418fff19.png]: https://img-blog.csdnimg.cn/49bb85d258c647b9a2168512418fff19.png