没有重复字符的最长子串：错误答案

Question

我花了几个小时试图找出方法 returns 对这个特定测试用例的错误答案的原因：“qrsvbspk”。该方法 returns 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;
    }
}

Answer 1

您的方法不正确，因为如果找到更长的子字符串，您只清除 Set 并重置 count，而您应该在外循环的每次迭代中执行此操作。

您可以使用两点法来提高效率。当左指针从 0 移动到小于 String 长度的 1 时，我们不断增加右指针，直到到达 Set 中已经存在的字符。之后，当前子串的长度为right - left，我们从Set中删除左边索引处的字符。由于两个指针最多可以增加 N 次（其中 N 是 String 的长度），此方法在 O(N).

中运行

public int lengthOfLongestSubstring(String s) {
    int max_count = 0;
    HashSet<Character> set = new HashSet();
    int left = 0, right = 0;
    while(left < s.length()){
        while(right < s.length() && set.add(s.charAt(right))){
            ++right;
        }
        max_count = Math.max(max_count, right - left);
        set.remove(s.charAt(left++));
    }
    return max_count;
}

没有重复字符的最长子串：错误答案

Longest Substring Without Repeating Characters: Wrong answer

java

hash

longest-substring