算法：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度（时间复杂度O(n)）

忘是亡心i 2022-01-26 15:09 128阅读 0赞

时间复杂度：O(2n) = O(n)O(2n)=O(n)，在最糟糕的情况下，每个字符将被 startIdx 和 endIdx 访问两次

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

**下面有注解版和无注解版**  
**无注释版：**

public static void longestSubString(String str) { 
    
    		int startIdx = 0;//开始索引
    		int endIdx = 0;	//结束索引
    		int longest = 0;//最大长度
    		int strLength = str.length();
    		HashSet<Character> hashSet = new HashSet<>();
    		StringBuilder longestSubStr = new StringBuilder();
    		String maxString = "";
    		while (startIdx < strLength && endIdx < strLength) { 
    			if (!hashSet.contains(str.charAt(endIdx))) { //asdasdfasdfgh
    				longestSubStr.append(str.charAt(endIdx));
    				hashSet.add(str.charAt(endIdx++));
    				longest = Math.max(longest, endIdx - startIdx);
    				if (maxString.length() < longestSubStr.length()) { 
    					maxString = longestSubStr.toString();
    				}
    			} else { 
    				hashSet.remove(str.charAt(startIdx++));
    				longestSubStr.delete(0, 1);
    			}
    		}
    		System.out.println("【"+str+"】最大长度:"+longest +",最长字符串:"+maxString);
    	}

**注释版：**

public static void longestSubString(String str) { 
    
    		int startIdx = 0;//开始索引
    		int endIdx = 0;	//结束索引
    		int longest = 0;//最大长度
    		//当前字符串长度
    		int strLength = str.length();
    		//无重复集合 判断元素是否存在
    		HashSet<Character> hashSet = new HashSet<>();
    		//记录无重复字符串
    		StringBuilder longestSubStr = new StringBuilder();
    		//记录最大无重复字符串
    		String maxString = "";
    		while (startIdx < strLength && endIdx < strLength) { 
    			if (!hashSet.contains(str.charAt(endIdx))) { //asdasdfasdfgh
    				longestSubStr.append(str.charAt(endIdx));
    				//元素不存在加入集合，结束索引向后移动一位
    				hashSet.add(str.charAt(endIdx++));
    				//计算出当前不重复字符串最大长度
    				longest = Math.max(longest, endIdx - startIdx);
    				if (maxString.length() < longestSubStr.length()) { 
    					maxString = longestSubStr.toString();
    				}
    			} else { 
    				//元素存在,删除开始索引的值，开始索引向后移动一位
    				hashSet.remove(str.charAt(startIdx++));
    				longestSubStr.delete(0, 1);
    			}
    		}
    		System.out.println("【"+str+"】最大长度:"+longest +",最长字符串:"+maxString);
    	}

测试：
    public static void main(String[] args) { 
    		longestSubString("abcabcbb");
    		longestSubString("bbbbb");
    		longestSubString("pwwkew");
    		longestSubString("asdasdfasd");
    		longestSubString("asdasdfasdfgh");
    }
    console:
    【abcabcbb】最大长度:3,最长字符串:abc
    【bbbbb】最大长度:1,最长字符串:b
    【pwwkew】最大长度:3,最长字符串:wke
    【asdasdfasd】最大长度:4,最长字符串:asdf
    【asdasdfasdfgh】最大长度:6,最长字符串:asdfgh