C++：寻找最长无重复子串 |21xrx.com

C++：寻找最长无重复子串

2023-07-05 14:16:51 深夜i 22 0

C++ 最长无重复子串字符串处理算法数据结构

C++是一种强大的编程语言，在算法问题中也能发挥很大的作用。当我们需要找到一个字符串中最长的无重复子串时，C++提供了方便的数据结构和算法来解决这个问题。

在C++中，我们可以使用一个unordered_set来存储字符串中的字符，并使用两个指针来表示子串的开头和结尾。我们可以遍历整个字符串，每次移动结尾指针，并将字符添加到unordered_set中。如果unordered_set中已经存在该字符，我们就移动开头指针，并从unordered_set中删除开头指针所指向的字符，直到unordered_set中不存在重复字符。

此时，我们记录下此时子串的长度，然后将其与之前记录的最大长度进行比较，保留较大的值。最后，我们就能得到整个字符串中最长的无重复子串的长度。

下面是一个例子程序，可以实现寻找最长无重复子串：

#include <unordered_set>
#include <iostream>
#include <string>
using namespace std;
int findMaxLength(string s) {
  unordered_set<char> set;
  int start = 0, end = 0, maxLength = 0;
  while (end < s.length()) {
    if (set.count(s[end])) {
      set.erase(s[start]);
      start++;
    } else {
      set.insert(s[end]);
      end++;
      maxLength = max(maxLength, end - start);
    }
  }
  return maxLength;
}
int main() {
  string s = "abcabcbb";
  int maxLength = findMaxLength(s);
  cout << maxLength << endl;
  return 0;
}

在这个例子程序中，我们将字符串s传给findMaxLength函数，并使用while循环处理字符串。在每一次循环中，我们将结尾指针end向后移动，并将字符添加到unordered_set中。如果该字符已经存在于unordered_set中，则说明有重复字符，此时我们移动开头指针start，并从unordered_set中删除开头字符，直到不再有重复字符为止。

同时，在每次添加字符时，我们记录下当前子串的长度，并与之前记录下的最大长度进行比较，保留较大的值。最后，我们就能得到整个字符串中最长的无重复子串的长度，并将其输出。

总结来说，使用C++来寻找最长无重复子串非常简单，只需要使用unordered_set来存储字符，并使用两个指针来表示子串的开头和结尾即可。当然，在实际应用中，我们还需要考虑一些极限情况以及代码的优化。但总的来说，C++提供了强大的工具和语法来解决这类问题，只需要理解原理，就能轻松编写高效的代码。

上一篇: idea打包java可执行jar包

下一篇: "C++和VB代码的速度比较"

评论区

相似文章