【LeetCode】3-无重复字符的最长子串
3-无重复字符的最长子串
题目描述
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
题解
方法一
根据题目可知，目的就是根据传入的字符串找到该字符串中不含重复字符的最长子串。例如有字符串pwwkew，其中不包含重复字符的子串有：pw，wk，ke，ew，wke，kew，这其中最长的就是最后面两个子串，长度都为 3，所以返回 3 即可。
根据题意，我们可以使用一个 List 来存放子串的字符，然后利用 List 自带的 contains 就可以判断是否有重复的字符。
使用一个变量 res 作为答案保存最长子串的长度，默认为 0，然后使用双重循环，外层循环通过下标 i 作为子串的起始位置，从第一个字符开始，内层循环从外层循环的下一个字符开始，循环时判断 List 中是否有重复的字符，如果没有重复的字符，则将字符添加到 List 中进行下一轮循环，如果有重复的字符则比较当前 List 的长度和 res 保存的长度，如果 List 的长度比 res 保存的大，则将 res 修改为 List 的长度，然后 i 后移一位，并清除 List 中的元素，继续循环。最后返回的 res 就是最长子串的长度。
public int lengthOfLongestSubstring(String s) { List<Character> list = new ArrayList<>(); int res = 0; for (int i = 0; i < s.length(); i++) { list.clear(); list.add(s.charAt(i)); for (int j = i + 1; j < s.length(); j++) { char c = s.charAt(j); if (list.contains(c)) { break; } list.add(c); } res = Math.max(res, list.size()); } return res;}最简单粗暴的方法，时间复杂度为：O(N^2)。
方法二
上述方法能够解决问题，但是太过于粗暴不够优雅，并且时间复杂度太高。
还可以使用滑动窗口的方式解决。
滑动窗口概念：使用两个指针一前一后的在字符串上移动，两个指针中间的部分随着前后指针的不断移动而变化，两个指针形成的中间部分就可以看做是一个窗口。示意图如下：
本题使用滑动窗口的方法，定义左指针 i 和一个右指针 j，同样使用 res 表示最大长度，默认为 0，使用 HashSet 保存字符。
首先左指针和右指针都指向字符串的位置 0，然后右指针不断的向右边移动，并且每移动一次就判断一下在 Set 中是否有和当前位置一样的元素，如果没有则将当前位置的元素加入到 Set 中，然后继续移动，如果有，则通过 Math.max 将更长的子串的长度赋值给 res，然后删除左指针指向的元素并将左指针向后移动一位（在代码中是通过 for 控制的左指针 i 的右移，所以都是先移动左指针 i ，然后删除 i - 1 位置的元素），然后继续比较右指针的指向的元素，如果 Set 中仍然包含，则继续将左指针右移，如果不包含，则将右指针指向的元素加入到 Set 中，并继续移动右指针，以此类推。
public int lengthOfLongestSubstring(String s) { int res = 0; int j = 0; Set<Character> set = new HashSet<>(); for (int i = 0; i < s.length(); i++) { if (i != 0) { set.remove(s.charAt(i - 1)); } while (j < s.length() && !set.contains(s.charAt(j))) { set.add(s.charAt(j)); j++; } res = Math.max(res, set.size()); } return res;}代码解析：
时间复杂度：O(N)
代码中在移除元素时判断了 i != 0，这是为了过滤掉第一轮循环 i = 0 时 Set 中还没有数据的情况。
公众号：良猿