LeetCode3 无重复字符的最长子串 Longest Substring Without Repeating Characters

LeetCode3 无重复字符的最长子串 Longest Substring Without Repeating Characters

题目描述

题目地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 题目难度：中等

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

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

分析

这道题我第一时间想到的是进栈和出栈的思路，首先我会判断集合中是否存有当前值，若已有则将前边的内容剔除掉，否则当前取出当前集合的数量，与当前最大值进行比对，遍历一次即可完成。

方法1：进栈出栈思想

public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int max = 0; int j = 0; for (int i = 0; i < s.length(); i++) { if (map.containsKey(s.charAt(i))) { i = map.get(s.charAt(i)) + 1; map = new HashMap<>(); max = Math.max(j, max); j = 1; } else { j++; } if (i == s.length() - 1) { max = Math.max(j, max); } map.put(s.charAt(i), i); } return max; }

耗时224ms，实在是有点惨，只战胜了12.38%提交记录

官方解答1：暴力法

思路：逐个检查所有的子字符串，看它是否不含有重复的字符。

这种方法处理速度过于缓慢，是最坏的解法。

时间复杂度为O(n^3)

public int lengthOfLongestSubstring1(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; }

官方解答2：滑动窗口

思路：过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

public int lengthOfLongestSubstring2(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); int ans = 0, i = 0, j = 0; while (i < n && j < n) { if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans = Math.max(ans, j - i); }else { set.remove(s.charAt(i++)); } } return ans; }

时间复杂度O(2n) = O(n)，最坏的情况下每个元素都会被i和j访问两次

官方解答3：优化的滑动窗口

思路：定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

public int lengthOfLongestSubstring3(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; }

相似题目

至多包含两个不同字符的最长子串

至多包含 K 个不同字符的最长子串

K 个不同整数的子数组

总结

​ 我认为优化的滑动窗口和我写的方法思路是一个思路，但是这种方法明显很巧妙，他通过找到重复字符的位置，然后比较时直接过滤掉前面的内容，而我则是通过重新创建一个新的map来达到这个效果，但是这个效果差异是真的大，新建对象的操作太过耗时，还有就是对最后一截字符串的处理，明显更为简便。

​ 另外，官方还有一种ASCII码替换的解法，主要思路是把匹配到的字符替换成ASCII码值，然后通过数组的方式代替map进行比对，这种方法这里就不作详细介绍了。