无重复字符的最长子串:错误答案

drkbr07n  于 2021-06-29  发布在  Java
关注(0)|答案(2)|浏览(229)

我花了几个小时试图找出为什么这个方法会为这个特定的测试用例返回错误的答案:“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;
    }
}
9w11ddsr

9w11ddsr1#

在回答中,物联网已经提到了问题背后的根本原因。我正在添加另一种方法来查找最长子串的长度。
使用嵌套循环,检查从一个位置开始到字符串结尾的所有子字符串中字符的唯一性。
更新的值 max (跟踪最长子串长度的变量)如果发现子串的长度更大。
演示:

public class Main {
    public static void main(String[] args) {
        // Test
        System.out.println(lengthOfLongestSubstring("qrsvbspk"));
    }

    public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length(); j >= i; j--) {
                int len = j - i;
                if (s.substring(i, j).chars().distinct().count() == len && len > max) {
                    max = len;
                }
            }
        }
        return max;
    }
}

输出:

5
smdnsysy

smdnsysy2#

你的方法不正确,因为你只清除了 Set 并重置 count 如果找到一个较长的子串,那么应该在外循环的每次迭代中这样做。
您可以使用双指针方法来提高效率。当左指针从 0 长度小于 String ,我们不断增加右指针,直到到达已在 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;
}

相关问题