题目

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

无重复字符的最长子串

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

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

示例 1:

 输入: s = "abcabcbb"
 输出: 3 
 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3

示例 2:

 输入: s = "bbbbb"
 输出: 1
 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

 输入: s = "pwwkew"
 输出: 3
 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

 输入: s = ""
 输出: 0
 

 0 <= s.length <= 5 * 104
 s 由英文字母、数字、符号和空格组成

Solution

解法

暴力思路

检查重复字符串的思路有哪些？

• 两次遍历循环字符串第一层循环记录头部信息第二层循环用来滑动数据将第二层数据存入到Set中存入之前判断Set中是否已经存在字符串有则BREAK，进入下一个外层循环计算最新的结果长度，并且将当前字符串存入到Set中每当第二次循环完成之后，清空Set，防止影响下一个第一层循环的数据

CODE

 class Solution {
      public int lengthOfLongestSubstring(String s) {
        int res = 0 ;
        Set<Character> set = new HashSet<>();
        for(int i = 0 ; i < s.length();i++){
            for(int j = i ; j < s.length() ; j++){
                if(set.contains(s.charAt(j))){
                   break;
                }
                if(j-i+1 > res){
                    res = j-i+1;
                }
                set.add(s.charAt(j));
            }
            set.clear();
        }
        return res;
     }
 }

复杂度

• 时间复杂度：O(N^2)，N 为S的长度

结果

• 执行用时：99 ms, 在所有 Java 提交中击败了12.37%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了39.62%的用户

双指针版本

解题思路

双指针，又名滑动窗口，其实就是一个队列，比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

1，从A ->ABC

当前Left为0，Right为2，整体的结果最大长度为3，缓存cache中已经有了数据{A:0,B:1,C:2}

2. ABCA

当再次遇到A时，缓存cache中已经存在了A字符串，我们需要比较【当前A在缓存中的位置】，与【当前Left的值】，如果Left的值小于等于A在缓存中的位置，那么我们需要调整Left的值为（A在缓存中的位置 + 1），这么做主要是为了Left坐标始终处于最新的重合点的位置的后面一位，组成新的不重合的长度

3. ABCAB

跟上面同理，当遇到B时，缓存中已经存在了B字符串，需要比较【当前B在缓存中的位置】，与【当前Left的值】，如果Left的值小于等于``B在缓存中的位置，那么久需要调整Left的值为（B在缓存中的位置+1），最终是为了Left坐标始终处于最新的重合点（B）的位置的后面一位，组成新的不重合的长度

CODE

 class Solution {
      public int lengthOfLongestSubstring(String s) {
          
        int length = s.length();
        if(length == 0){
            return 0;
        }
        int res = 0 ;
        //快指针
        int right = 0 ;
        //慢指针 
        int left = 0 ;
        //索引，空间换时间
        Map<Character,Integer> map = new HashMap<>();
        for(;right<length;right++){
            Character c = s.charAt(right);
         if(map.containsKey(c)){
             //更新left
             if( map.get(c) >= left){
                     left = map.get(c)+1;
             }
         }
         //更新结果res
         if((right-left+1)>res){
                 res = (right-left+1);
         }
          //更新c的位置
         map.put(c,right);
 
        }
        return res ;
     }
 }

复杂度

• 时间复杂度：O(N)，N为字符串长度

结果

• 执行用时：7 ms, 在所有 Java 提交中击败了79.24%的用户

• 内存消耗：38.8 MB, 在所有 Java 提交中击败了28.63%的用户

参考

https://www.bilibili.com/video/BV1St4y1k72y?from=search&seid=12825150742902127069

https://www.bilibili.com/video/BV1r7411X7mJ?from=search&seid=15075195474456497360