无重复字符的最长子串 题目描述 给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例 示例 1:
1 2 3 输入:"abcabcbb" 输出:3 解释:因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
1 2 3 输入:"bbbbb" 输出:1 解释:因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
1 2 3 输入:"pwwkew" 输出:3 解释:因为无重复字符的最长子串是 "wke",所以其长度为 3。
限制 请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
题目来源:力扣(LeetCode) 题目链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一 这题我一开始用到的是比较暴力的方法,直接取出所有的子串,再判断每个子串中是否含有重复字符,并记录最长的不含重复字符的子串长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.util.HashMap;import java.util.Map;class Solution { public int lengthOfLongestSubstring (String s) { int max = 0 ; for (int i = 0 ; i < s.length(); i++) { for (int j = i; j < s.length() + 1 ; j++) { String sub = s.substring(i, j); if (this .check(sub)) { max = Math.max(max, sub.length()); } else { break ; } } } return max; } public boolean check (String str) { Map<Character, Character> map = new HashMap<>(); for (int i = 0 ; i < str.length(); i++) { char ch = str.charAt(i); Character ret = map.put(ch, ch); if (ret != null ) { return false ; } } return true ; } }
不出意料,这种解法直接超时了。
解法二 解法二是我对解法一的一点点优化。在第二层循环中移动右指针时,如果遇到了重复的字符就直接结束该层循环,将左指针右移一位,开始下一次循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.HashMap;import java.util.Map;class Solution { public int lengthOfLongestSubstring (String s) { int max = 0 ; for (int i = 0 ; i < s.length(); i++) { Map<Character, Character> map = new HashMap<>(); for (int j = i; j < s.length(); j++) { Character c = s.charAt(j); Character ch = map.put(c, c); if (ch != null ) { max = Math.max(max, j - i); break ; } } } return max; } }
优化一些后的解法以 110 ms 的成绩通过了测试,但是和优秀题解还是有不小的差距。
解法三 我看了一下官方的题解,官方采用了一种叫滑动窗口的方法。我发现在题解二中的优化还不够充分,没有利用到上一次外层循环中的判重结果,参考官方题解后重新写出以下解法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.HashSet;import java.util.Set;public class Solution { public int lengthOfLongestSubstring (String s) { int left; int right = 0 ; int ans = 0 ; Set<Character> set = new HashSet<>(); Character ch; for (left = 0 ; left < s.length(); left++) { while (right < s.length()) { ch = s.charAt(right); if (set.contains(ch)) break ; set.add(ch); right++; } ans = Math.max(right - left, ans); set.remove(s.charAt(left)); } return ans; } }
这种解法的时间直接降到了 8 ms。