C++求不重复出现的最短子串 |21xrx.com

C++求不重复出现的最短子串

2023-06-27 04:55:15 深夜i -- --

C++ 不重复最短子串

最近在学习C++，遇到了一个问题。需要求一个字符串中不重复出现的最短子串。经过一番思考后，我想到了一种解决方案。

首先，定义一个指针start和一个指针end，分别指向字符串的开头和结尾。然后，利用哈希表记录每个字符最后一次出现的位置。从start向end遍历字符串，如果当前字符在哈希表中不存在，就将它加入哈希表，并将end指针向后移动。如果当前字符已经出现过，那么就找到它上次出现的位置，并将start指针移到那个位置的后一位。此时，我们就找到了一个不重复出现的子串，计算它的长度，并将它和之前的所有子串长度比较，得到最短的那个。

代码实现如下：


#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int shortestSubstring(string s) {
  int start = 0, end = 0;
  int minLength = s.size();
  unordered_map<char, int> lastPos; // 哈希表记录最后出现的位置
  for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (lastPos.find(c) != lastPos.end() && lastPos[c] >= start) { // 如果这个字符之前出现过
      start = lastPos[c] + 1; // 移动start指针到上次出现的位置后一位
    }
    lastPos[c] = i; // 记录这个字符最近一次出现的位置
    end = i + 1; // end指针后移
    if (end - start < minLength) // 如果找到了不重复的子串
      minLength = end - start; // 计算它的长度
    
  }
  return minLength;
}
int main() {
  string s = "abcabcbb";
  int result = shortestSubstring(s);
  cout << result << endl; // 输出结果为3，即"abc"
  return 0;
}

以上就是我在学习C++中遇到的问题和解决方案。希望能对其他初学者有所帮助。

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

下一篇: NodeJS请求转发

评论区

()

相似文章