Given a string, find the length of the longest substring without repeating characters. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商
Given a string, find the length of the longest substring without repeating characters.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题目一拿到手,想都不用想,直接暴力遍历。然而结果虽然可行,但是效率太低,最终还有一个案例没通过,晕。还是要多动脑啊
public int lengthOfLongestSubstring(String s) { int length = 0; if(isUnique(s)) { length = s.length(); } int index = s.length(); for(int i = 0; i < index; i++) { for(int j = index; j >= i; j--) { String str = s.substring(i, j); if(isUnique(str) && str.length() > length) { //从字符串的后面往前遍历,遇到第一个符合条件的肯定就是最长的之一,因此不用再往前遍历了 length = str.length(); break; } //剩下的子字符串的长度小于等于暂时的结果,也无需再往前遍历 if(j - i <= length) { break; } } } return length; } public boolean isUnique(String s) { Set<Character> set = new HashSet<Character>(); char[] chars = s.toCharArray(); for(char c: chars) { set.add(c); } return (set.size() == s.length()); }
无论怎么去优化,最终还是有一个案例没能通过。貌似暴力解法在此题行不通??
看到各种题解都提及到滑动窗口解法,于是去查了一下这个算法的思想,并根据自己的理解去写一下代码,终于通过了,虽然还有很大的提升空间...
public int lengthOfLongestSubstring(String s) { int result = 0; int left = 0; //窗口左边界 int right = 0; //窗口右边界 int length = s.length(); Set<Character> set = new HashSet<Character>(); while(left < length && right < length) { int temp = 0; if(!set.contains(s.charAt(right))) { set.add(s.charAt(right)); right++; temp = set.size(); if(temp > result) { result = temp; } } else { //如果发现set中已经存在此字符,就把左边界右移 set.remove(s.charAt(left)); left++; } } return result; }