题目描述
blablabla
样例
blablabla
算法1
整体框架还是用的双指针,但是这里就是改进了一下删除重复和记录重复的方法。
直接把当前的位置记录下来,然后遇到重复数字的时候可以直接恢复,具体做法在代码的注释中。
时间复杂度
参考文献
C++ 代码
//用前后指针,前指针在前面走,后指针在后面跟
//前头指针j开始遍历,如果这个字符对应的位置是-1,说明没有被访问,就把它赋值为当前的位置
//如果当前字符位置不是-1,就说明已经有重复了,这时候就把后面的指针i移动到位置中记录的标号的后1位
//但是要注意判断,要移动的位置必须在当前i的后面
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
if(s.empty()) return 0;
vector<int> m(30, -1);
int res = 0;
for(int i = 0, j = 0; j < s.size(); ++j)
{
int t = s[j] - 'a';
if(m[t] != -1)//如果扫到重复的数字了,那就是s[j]这个字符重复了
{
i = max(m[t] + 1, i);//置位成重复元素的下一个,注意要判断重复的序号是否是大于当前的i,不能走回头路
}
m[t] = j;
res = max(res, j - i + 1);
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla