JZ48 最长不含重复字符的子字符串

描述

请从字符串中找出一个最长的不包含重复字符的子字符串             ，计算该最长子字符串的长度
  
  
  
  
  
  。 示例1 输入："abcabcbb" 返回值：3 说明：因为无重复字符的最长子串是"abc"
  
 
  
 
  
 
  
 
  
 
  
 
，所以其长度为 3  
  
  
  
  
  
 。

方法1

思路

维护一个数组











，想里面添加元素 
  
  
  
  
  
  ，直至出现第一个重复元素位置
  
  
  
  
  
  
，计算数组长度作为一次结果 将每一个元素都作为开始元素
 


 


 


 


 


 

，利用两次for 
 
 
 
 
 
 ，将全部不重复子字符串全部计算出来
   
   
   
   
   
   
，取出最大数

代码

int max = Integer.MIN_VALUE; List<Character> tmp = new ArrayList<>(); if(s == null && s.length() == 0) return 0; for(int i = 0; i < s.length(); i++) { for(int j = i; j < s.length(); j++) { if(tmp.contains(s.charAt(j))) break; tmp.add(s.charAt(j)); } max = Math.max(max, tmp.size()); tmp.clear(); } return max;

方法2

思路

既然要找一段连续子串的内不重复的长度
 

 

 

 

 

 
，我们可以使用滑动窗口 

 

 

 

 

 

 ，保证窗口内都是不重复的            ，然后窗口右界不断向右滑

 
 

 
 

 
 

 
 

 
 

 
 
，如果窗口内出现了重复字符











，说明新加入的元素与之前的重复了                   ，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的
 


 


 


 


 


 


。 具体做法: step 1：构建一个哈希表
 
 
 
 
 
 
 
 
 
 
 
 
，用于统计字符元素出现的次数
 
 
 
 
 
 。 step 2：窗口左右界都从字符串首部开始

















，每次窗口优先右移右界             ，并统计进入窗口的元素的出现频率   
   
   
   
   
   
 。 step 3：一旦右界元素出现频率大于1
  
 
  
 
  
 
  
 
  
 
  
 
，就需要右移左界直到窗口内不再重复











，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1 
  
  
  
  
  
  ，保证哈希表中的频率都是窗口内的频率
 

 

 

 

 

 

。 step 4：每轮循环
  
  
  
  
  
  
，维护窗口长度最大值

 

 

 

 

 

 。

代码

HashMap<Character, Integer> map = new HashMap<>(); int res = 0; for (int left = 0, right = 0; right < s.length(); right++) { //标记重复的元素 if (map.containsKey(s.charAt(right))) { //窗口右移进入哈希表统计出现次数 map.put(s.charAt(right), map.get(s.charAt(right)) + 1); } else { map.put(s.charAt(right), 1); } //左边界向右移知道没有重复元素 while (map.get(s.charAt(right)) > 1) { map.put(s.charAt(left), map.get(s.charAt(left++)) - 1); } //维护子字符串最大长度 res = Math.max(res, right - left + 1); } return res;

整体代码

package mid.JZ48最长不含重复字符的子字符串; import java.util.*; public class Solution { /** * 代码中的类名
  
  
  
  
  
  、方法名  
  
  
  
  
  
 、参数名已经指定
 


 


 


 


 


 

，请勿修改 
 
 
 
 
 
 ，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int lengthOfLongestSubstring (String s) { // write code here //方法1 /*int max = Integer.MIN_VALUE; List<Character> tmp = new ArrayList<>(); if(s == null && s.length() == 0) return 0; for(int i = 0; i < s.length(); i++) { for(int j = i; j < s.length(); j++) { if(tmp.contains(s.charAt(j))) break; tmp.add(s.charAt(j)); } max = Math.max(max, tmp.size()); tmp.clear(); } return max;*/ //方法2 HashMap<Character, Integer> map = new HashMap<>(); int res = 0; for (int left = 0, right = 0; right < s.length(); right++) { //标记重复的元素 if (map.containsKey(s.charAt(right))) { //窗口右移进入哈希表统计出现次数 map.put(s.charAt(right), map.get(s.charAt(right)) + 1); } else { map.put(s.charAt(right), 1); } //左边界向右移知道没有重复元素 while (map.get(s.charAt(right)) > 1) { map.put(s.charAt(left), map.get(s.charAt(left++)) - 1); } //维护子字符串最大长度 res = Math.max(res, right - left + 1); } return res; } public static void main(String[] args) { System.out.println(new Solution().lengthOfLongestSubstring("Kzz8")); } }