我花了几个小时试图找出为什么这个方法会为这个特定的测试用例返回错误的答案:“qrsvbspk”。方法返回6而不是5。我搞不清楚出了什么事。请救命!
我的方法是:
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int max_count = -1;
int count = 0;
if(s.length() == 0)
return 0;
HashSet<Character> set = new HashSet();
int k = 0;
while(k < s.length()){
i = k;
while(i < s.length() && !set.contains(s.charAt(i))){
count++;
set.add(s.charAt(i++));
}
if(count >= max_count){
max_count = count;
set.clear();
count = 0;
}
k++;
}
return max_count;
}
}
2条答案
按热度按时间9w11ddsr1#
在回答中,物联网已经提到了问题背后的根本原因。我正在添加另一种方法来查找最长子串的长度。
使用嵌套循环,检查从一个位置开始到字符串结尾的所有子字符串中字符的唯一性。
更新的值
max
(跟踪最长子串长度的变量)如果发现子串的长度更大。演示:
输出:
smdnsysy2#
你的方法不正确,因为你只清除了
Set
并重置count
如果找到一个较长的子串,那么应该在外循环的每次迭代中这样做。您可以使用双指针方法来提高效率。当左指针从
0
长度小于String
,我们不断增加右指针,直到到达已在Set
. 之后,当前子串的长度为right - left
我们把左边索引处的字符从Set
. 因为两个指针最多都可以增加N
次数(其中N
长度是String
),这种方法在O(N)
.