查找最长且不重复字符的子串

Question

我正在尝试解决 LeetCode 3：没有重复字符的最长子串。

我正在实现滑动窗口方法，该方法包括使用左指针和右指针来收缩和展开窗口。我还使用

std::set

来存储字符串的字符。

#include <iostream>
#include <set>
#include <algorithm>    //for std::max()


//Sliding window
int lengthOfLongestSubstring(std::string s)
{
    std::set<char> charSet;       
    int length = s.size();
    int left = 0;
    int right;
    int longest = 0;      //value we should return


    for(right = 0; right < length; right++) 
    {
        char c = s[right];  //get each element of the string


        //if character already exist in the set
        while (charSet.count(c)) //while we found a character that is a duplicate, we'll contract the window by increase the left pointer + 1
        {
            charSet.erase(s[left]);      //removing the element where left pointer is pointing at
            left += 1;                      //increase the left pointer
        }

        charSet.insert(c); //store the current element into the set

        int w = left - right + 1;           //calculate window length
        longest = std::max(longest, w);     //update longest with longest current window length
    }

    return longest;

}


int main()
{
    std::string s{"abcabcbb"};

    std::cout << lengthOfLongestSubstring(s);

    return 0;
}

输出：

2

正确的输出应该是3。

更新： 将窗口长度公式固定为

w = right - left + 1

并将

charSet.insert(c);

的位置更改为 while 循环结束后解决了问题。 这是更正后的 for 循环：

for(right = 0; right < length; right++) 
{
    char c = s[right];  //get each element of the string
    while (charSet.count(c)) 
    {
        charSet.erase(s[left]);      
        left += 1;                     
    }
    charSet.insert(c); 
    int w = right - left + 1;           
    longest = std::max(longest, w);     
}

Answer 1

问题来自于

left

和

right

反转的宽度计算。

这里有一个提案，允许使用提供简单的类似容器类型的模板参数来自定义

lengthOfLongestSubstring

。

因此，您可以使用不同的实现，例如与您的解决方案相同的

CharactersBag

（复杂性为

O(log(n))

）和使用简单数组的

CharactersBagOptim

（复杂性为

O(1)

）。

#include <iostream>
#include <set>
#include <array>
#include <algorithm>    //for std::max()

//Sliding window
template<typename BAG>
int lengthOfLongestSubstring (std::string const& s)
{
    std::set<char> charSet;       
    int left    = 0;
    int longest = 0;      //value we should return

    BAG bag;
    
    for (int right = 0; right < s.size(); right++) 
    {
        char c = s[right];  //get each element of the string

        //if character already exist in the set
        while (bag.contains(c)) //while we found a character that is a duplicate, we'll contract the window by increase the left pointer + 1
        {
            bag.erase(s[left]);      //removing the element where left pointer is pointing at
            left += 1;               //increase the left pointer
        }

        bag.insert (c); //store the current element into the set

        int w   = right - left + 1;           //calculate window length
        longest = std::max(longest, w);     //update longest with longest current window length
    }

    return longest;
}

////////////////////////////////////////////////////////////
struct CharactersBag
{
    std::set<char> items;       
    void insert   (char c) { items.insert(c); }
    bool contains (char c) { return items.find(c) != items.end(); }
    void erase    (char c) { items.erase(c);  }
};

////////////////////////////////////////////////////////////
struct CharactersBagOptim
{
    std::array<bool,256> items {false};       
    void insert   (char c) { items[c] = true;  }
    bool contains (char c) { return items[c];  }
    void erase    (char c) { items[c] = false; }
};

////////////////////////////////////////////////////////////
int main()
{
    std::string s{"abcabcbb"};

    std::cout << lengthOfLongestSubstring<CharactersBag>      (s) << "\n";
    std::cout << lengthOfLongestSubstring<CharactersBagOptim> (s) << "\n";

    return 0;
}

演示