无重复字符的最长子串

灰太狼 2022-01-22 03:05 188阅读 0赞

## 题目描述 ##

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

示例 1:

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

示例 2:

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

示例 3:

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

## 解法1，直接遍历 ##

直接遍历，遇到重复则回退

public int lengthOfLongestSubstring(String s) { 
    		if(s == null) { 
    			return 0;
    		}
    		int max=0;
    		Set<Character> set = new HashSet<Character>();
    		for(int i=0;i<s.length();i++) { 
    			if(set.contains(s.charAt(i))) { 
    				max = Math.max(max, set.size());
    				//回退
    				i= i-set.size()+1;
    				set.clear();
    			}
    			set.add(s.charAt(i));
    		}
    		return Math.max(max, set.size());
        }

## 优化解法1 ##

优化回退位置到第一个重复元素。  
其实还可以优化到不回退，只是删除重复及之前的元素，达到线性遍历，但是需要额外空间，意义不大。

public int lengthOfLongestSubstring(String s) {
    		if(s == null) {
    			return 0;
    		}
    		int max=0;
    		Map<Character, Integer> map = new HashMap<Character, Integer>();
    		for(int i=0;i<s.length();i++) {
    			if(map.containsKey(s.charAt(i))) {
    				max = Math.max(max, map.size());
    				//回退
    				i = map.get(s.charAt(i))+1;
    				map.clear();
    			}
    			map.put(s.charAt(i), i);
    		}
    		return Math.max(max, map.size());
        }

## 思路2：双指针&滑动窗口 ##

暴力法非常简单，但它太慢了。那么我们该如何优化它呢？

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 ii 到 j - 1j−1 之间的子字符串 s\_\{ij\}s  
ij  
  
已经被检查为没有重复字符。我们只需要检查 s\[j\]s\[j\] 对应的字符是否已经存在于子字符串 s\_\{ij\}s  
ij  
  
中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2)O(n  
2  
) 的算法，但我们可以做得更好。

通过使用 HashSet 作为滑动窗口，我们可以用 O(1)O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 \[i, j)\[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 \[i, j)\[i,j) 向右滑动 11 个元素，则它将变为 \[i+1, j+1)\[i+1,j+1)（左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 \[i, j)\[i,j)（最初 j = ij=i）中。 然后我们向右侧滑动索引 jj，如果它不在 HashSet 中，我们会继续滑动 jj。直到 s\[j\] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 ii 开头。如果我们对所有的 ii 这样做，就可以得到答案。

public int lengthOfLongestSubstring(String s) { 
    		if(s == null) { 
    			return 0;
    		}
    		int max=0, n =s.length();
    		int fast=0, slow=0;
    		Set<Character> set = new HashSet<Character>();
    		while(fast<n && slow<n) { 
    			if(!set.contains(s.charAt(fast))) { 
    				set.add(s.charAt(fast++));
    				max = Math.max(max, fast-slow);
    			}else { 
    				set.remove(s.charAt(slow++));
    			}
    		}
    		return max;
        }

## 思路2滑动窗口优化 ##

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果 s\[j\] 在 \[i, j) 范围内有与 j’ 重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 \[i，j’\] 范围内的所有元素，并将 ii 变为 j’ + 1。

**Java（使用 HashMap）**

public int lengthOfLongestSubstring(String s) { 
    	int n=s.length(), max=0;
    	Map<Character, Integer> map = new HashMap<Character, Integer>();
    	int i=0,j=0;
    	for(;j<n;j++) { 
    		if(map.containsKey(s.charAt(j))) { 
    			//需要跳跃就一步到位，跳到指定位置
    			i = Math.max(i, map.get(s.charAt(j)));
    		}
    		max = Math.max(max, j-i+1);
    		map.put(s.charAt(j), j+1);
    	}
    	return max;
    }

**Java（假设字符集为 ASCII 128）**

以前的我们都没有对字符串 s 所使用的字符集进行假设。

当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

*  int \[26\] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
 *  int \[128\] 用于ASCII码
 *  int \[256\] 用于扩展ASCII码

Java（使用有限字符集）

public int lengthOfLongestSubstring(String s) { 
    	int n=s.length(), max=0;
    	int[] arr = new int[128];
    	int i=0,j=0;
    	for(;j<n;j++) { 
    		//需要跳跃就一步到位，跳到指定位置
    		i = Math.max(i, arr[s.charAt(j)]);
    		max = Math.max(max, j-i+1);
    		arr[s.charAt(j)] = j+1;
    	}
    	return max;
    }