3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：
1. 两个指针，一个指针指针 i 指向当前元素 i，另一个指针 j 不断往后探测，直到遇到一个在 (j - i) 区间中有重复的数字，j - i 即为以 i 为起点的最长不重复子串的长度
2. 用一个HashSet存储 j 探测到的没有重复的字符，j每后移一个就添加一个字符，i每后移一个就删除一个字符，如果 j 遇到重复字符后会等i越过这个字符才会继续往后探测
1 class Solution { 2 public int lengthOfLongestSubstring(String s) { 3 // 4 5 // j - i即为以i为起点的最长不重复子串的长度 6 7 // 一个HashSet，保存从i到j的所有不重复字符 8 HashSet<Character> set = new HashSet<>(); 9 int j = 0; 10 int n = s.length(); 11 int len = 0; 12 for(int i = 0; i < n; i++){ 13 if(i != 0){ 14 set.remove(s.charAt(i - 1)); // 移除前一个字符 15 } 16 // 不重复则后移 17 for(;j < n && !set.contains(s.charAt(j));j++){ 18 set.add(s.charAt(j)); 19 } 20 len = Math.max(len, j - i); 21 } 22 return len; 23 } 24 }
复杂度分析：
i， j 指针均需遍历一次字符串，所以时间复杂度为O(2n), 也就是O(n)
空间复杂度的话，主要是看set集合存储字符的个数，最多存储字符串的长度个字符，所以空间复杂度为O(n)