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
     
       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)