题目描述
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: s = "abcabcbb"
输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其
长度为 3。
示例2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
思路
滑动窗口:
我们先用一个例子考虑如何在较优的时间复杂度内通过本题。我们不妨以示例一中的字符串abcabcbb为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:
- 以(a)bcabcbb开始的最长字符串为(abc)abcbb
- 以a(b)cabcbb开始的最长字符串为a(bca)bcbb
- 以ab(c)abcbb开始的最长字符串为ab(cab)cbb;
- 以abc(a)bcbb 开始的最长字符串为abc(abc)bb;
- 以abca(b)cbb开始的最长字符串为abca(bc)bb;
- 以abcab(c)bb开始的最长字符串为abcab(cb)b;
- 以abcabc(b)b开始的最长字符串为abcabc(b)b;
- 以abcabcb(b) 开始的最长字符串为abcabcb(b)。
由上述例子我们可以看到,如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第k 个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1个字符作为起始位置时,首先从k+1到rk的字符显然是不重复的,并且由于少了原本的第k 个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。这样一来,我们就可以使用「滑动窗口」来解决这个问题了:
- 我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的rk;
- 在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;
- 在枚举结束后,我们找到的最长的子串的长度即为答案。
判断重复字符:
在上面的流程中,我们还需要使用一种数据结构来判断 是否有重复的字符,常用的数据结构为哈希集合(即 C++ 中的 std::unordered_set)。在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。
至此。该题完美被解决。
代码:
#include <iostream> #include <string> #include <unordered_set> using namespace std;
int func(string s){ unordered_set<char> uns; int index = 0; // 滑动窗口的右索引,起始下标为0 int max_length = 0; // 目前找到了最大不重复字串长度 int n = s.size(); for(int i=0; i<n; i++){ // i就是滑动窗口的左索引 if(i != 0){ uns.erase((s[i-1])); // 把此次遍历起始索引的前一位从当前哈希表中删除 } while(index < n){ if(uns.count(s[index]) != 0) // 遇到重复的字符就跳出循环 break; uns.insert(s[index]); index++; } max_length = max(max_length, index-i); } return max_length; }
标签:子串,字符,--,重复,字串,字符串,最长,指针 From: https://www.cnblogs.com/sunjuil/p/17392199.html