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

示例 1:

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

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

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

思路：

一个set记录i到j遇到的所有字母。

两个指针，符合条件就更新答案，并且右指针向右。

不符合就删除左指针相应的值， 并继续尝试。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 public int lengthOfLongestSubstring(String s) {
     
    
   

    

     

    
    

     
 int n = s.length();
     
    
   

    

     

    
    

     

       Set<Character> set = new HashSet<>();
     
    
   

    

     

    
    

     
 int ans = 0, i = 0, j = 0;
     
    
   

    

     

    
    

     
 while (i < n && j < n) {
     
    
   

    

     

    
    

     
 // try to extend the range [i, j]
     
    
   

    

     

    
    

     
 if (!set.contains(s.charAt(j))){
     
    
   

    

     

    
    

     
 set.add(s.charAt(j++));
     
    
   

    

     

    
    

     

       ans = Math.max(ans, j - i);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else {
     
    
   

    

     

    
    

     
 set.remove(s.charAt(i++));
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

优化

第一：可以用map记录一下遇到的char的下标是多少，这样我们缩i的时候不用一个一个缩，而是直接到该去的位置

第二：可以不用map，因为字符种类有限，用数组记录（桶排序思想）

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 public int lengthOfLongestSubstring(String s) {
     
    
   

    

     

    
    

     
 int n = s.length(), ans = 0;
     
    
   

    

     

    
    

     
 int[] index = new int[128];
     
    
   

    

     

    
    

     
 for (int j = 0, i = 0; j < n; j++) {
     
    
   

    

     

    
    

     

       i = Math.max(index[s.charAt(j)], i);
     
    
   

    

     

    
    

     

       ans = Math.max(ans, j - i + 1);
     
    
   

    

     

    
    

     

       index[s.charAt(j)] = j + 1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103240545