写一个C++的函数,该函数返回一个string,函数的需求是给你一个字符串s,你需要返回字符串s中无重复字符的最长子串
时间: 2024-09-06 17:04:38 浏览: 39
为了实现这个需求,我们可以使用滑动窗口的方法来遍历字符串,同时使用一个集合(或哈希表)来记录窗口内的字符是否出现过。以下是C++函数的实现代码:
```cpp
#include <string>
#include <unordered_set>
std::string longestSubstringWithoutRepeatingChars(const std::string& s) {
std::unordered_set<char> charSet;
int left = 0, right = 0;
int maxLength = 0;
std::string longestSubstring;
while (right < s.length()) {
if (charSet.find(s[right]) == charSet.end()) {
// 如果字符s[right]还未出现过,加入到字符集中
charSet.insert(s[right]);
// 右指针向右移动
right++;
// 更新最长无重复字符子串的长度
if (right - left > maxLength) {
maxLength = right - left;
longestSubstring = s.substr(left, maxLength);
}
} else {
// 如果字符s[right]已经出现过,移除左边界字符,并移动左指针
charSet.erase(s[left]);
left++;
}
}
return longestSubstring;
}
```
这个函数首先定义了一个`unordered_set`来存储当前窗口内的字符,然后使用左右两个指针`left`和`right`来定义当前考虑的子串窗口。函数会不断地向右移动`right`指针来扩展窗口,直到遇到一个已经存在于`charSet`中的字符。当这种情况发生时,函数会移动`left`指针,直到窗口内没有重复字符为止。在每次窗口更新时,都会检查并更新最长无重复字符子串的信息。
阅读全文