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

Question

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

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;
}

Answer 2

类解决方案 { 民众： int lengthOfLongestSubstring(字符串 s) { 整数 l = 0; 矢量p；

      for (int i = 0; i < s.size(); i++)
      {
        auto target= s[i];
        auto current = p.begin();
        auto it = find(current, p.end(), target);
        
        if (it == p.end())
        {
           p.push_back(target);
          
        }

        else 
        {
            l = std::max(l, static_cast<int>(p.size()));
            p.erase(p.begin(), it + 1);
            p.push_back(target);
        }
      }
       l = std::max(l, static_cast<int>(p.size()));
    return l;
    }