回归次数：1
题目：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解答：
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
/**
* 最基础遍历,时间复杂度：O(n ^3) 性能很差
* @param s
* @return
*/
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for(int i = 0;i < n;i ++){
for(int j = i + 1;j <= n;j ++){
if (allUnique(s,i,j)){
ans = Math.max(ans,j - i);
}
}
}
return ans;
}
public boolean allUnique(String s,int start,int end){
Set<Character> set = new HashSet<>();
for(int i = start;i < end;i ++){
Character ch = s.charAt(i);
if (set.contains(ch))return false;
set.add(ch);
}
return true;
}
/**
* 滑动窗口 会把最大的不重复字符串留住，最后留在窗口里面的不一定是最大的不重复字符串
* 空间复杂度：O(2n) = O(n)
* @param s
* @return
*/
public int lengthOfLongestSubstring2(String s) {
int n = s.length();
int ans = 0 , i = 0, j = 0;
Set set = new HashSet();
while (i < n && j< n){
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j));
j += 1;
ans = Math.max(ans,j - i);
}else{
set.remove(s.charAt(i));
i += 1;
}
}
return ans;
}
/**
* 滑动窗口优化，Set改为Map存储，减少了查找对比的时间复杂度
* @param s
* @return
*/
public int lengthOfLongestSubstring3(String s) {
int n = s.length();
int ans = 0 , i = 0, j = 0;
/**
* 使用map减少了比对的时候的查找时间复杂度，不需要遍历整个set，O(n),map直接O(1)查找对比
*/
Map<Character,Integer> map = new HashMap();
while (i < n && j< n){
if (!map.containsKey(s.charAt(j))){
map.put(s.charAt(j),j);
j += 1;
ans = Math.max(ans,j - i);
}else{
map.remove(s.charAt(i));
i += 1;
}
}
return ans;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lengthOfLongestSubstring3("pwwkew"));
}
}
网友评论