21xrx.com
2024-12-23 00:12:23 Monday
登录
文章检索 我的文章 写文章
C++实现最长不重复子串问题
2023-06-30 15:46:06 深夜i     --     --
C++ 最长不重复子串 实现

最长不重复子串问题是一种经典的字符串处理问题,其定义为在一个字符串中找到一个最长的子串,使得该子串中没有重复的字符。例如,在字符串“abcabcbb”中,最长不重复子串是“abc”,长度为3。

C++是一种常用的编程语言,可以很方便地实现最长不重复子串问题。以下是一个基于滑动窗口算法的C++实现:


#include <iostream>

#include <unordered_set>

using namespace std;

int longestSubstring(string s) {

  unordered_set<char> uniq_chars;

  int left = 0, ans = 0;

  for (int right = 0; right < s.size(); right++) {

    while (uniq_chars.find(s[right]) != uniq_chars.end()) {

      uniq_chars.erase(s[left]);

      left++;

    }

    uniq_chars.insert(s[right]);

    ans = max(ans, right - left + 1);

  }

  return ans;

}

int main() {

  string s = "abcabcbb";

  int ans = longestSubstring(s);

  cout << ans;

}

在上面的代码中,我们使用了一个unordered_set数据结构来记录窗口中的唯一字符。为了实现滑动窗口算法,我们使用了两个指针left和right来维护窗口的起始和结束位置。

在每一次循环中,我们使用while循环来移动left指针,直到窗口中不包含重复的字符。然后我们将当前right指向的字符添加到窗口中,并记录当前的最长不重复子串长度。

最后,我们返回ans,即最长不重复子串长度。

总之,C++可以很方便地实现最长不重复子串问题。如果你需要解决类似的字符串处理问题,可以尝试使用滑动窗口算法或其他相关算法进行实现。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复