题目： 无重复字符的最长子串
描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
leetcode链接
方法一：滑动窗口（双指针)
设定两个指针left和right指向最长子串的头部和尾部的下一个元素，left和right初始分别为0和1，对于right指向的每一个元素我们都在前面left和right区间内寻找是否出现过，若未出现过，则把它加入子串中，，right指针右移，若出现过，left指针移动到出现的元素后一个位置，right指针移动到出现的元素后两个位置，最后再更新最长子串的长度
时间复杂度：o(n²) 需要遍历一遍字符串的时间复杂度为o(n),对于每一个新加入的元素都需要进行查找操作，时间复杂度为o(n)，因此总时间复杂度为o(n²)
空间复杂度：o(1) 都在原字符串上进行操作，无需占用新的内存空间
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n==1){//字符串只有一个元素，那么最长无重复子串长度也为1
return 1;
}
int left = 0,right = 1;
int maxLen = 0;
while(right<n){
int i = left;
//在子串中查找相同的元素
while(s[right]!=s[i]&&i<right){
i++;
}
if(i==right){
//没有相同的元素则加入子串中
right++;
}else{
left = i+1;
right = i+2;
}
//更新最大的子串长度
maxLen = max(maxLen,right-left);
}
return maxLen;
}
方法二：滑动窗口+哈希表判断重重复元素
对于方法一中我们判断重复元素需要遍历一遍子数组，时间复杂度为o(n),因此我们考虑用哈希表来优化查找重复元素的时间，我们把子数组的每一个元素存储到哈希表中，哈希表查找的时间复杂度为o(1)，同样的我们定义两个指针left和right，left
指向子数组的起始位置，right指向待加入的元素，然后我们利用count（）判断right指向的元素是否在子数组中存在，如果不存在，那么加入哈希表中，如果存在删除哈希表中键为s[left]的元素，然后left右移动，循环此操作直到right指向的元素在子数组中不出现为止，最后维护最大的子数组长度。
时间复杂度：o（n）left，right指针均只会向右移动，遍历一遍字符串，时间复杂度为o（n）
空间复杂度：o（n）哈希表的空间为o（n）
int lengthOfLongestSubstring(string s) {
int n = s.size();
int left = 0,right = 0;
int maxLen = 0;
unordered_map<char,int> map;
while(right<n){
while(left<right&&map.count(s[right])){
//删除有重复字符的子串直至不出现重复的字符
map.erase(s[left++]);
}
//把right指向的元素当成关键字插入map
map[s[right++]] = 0;
maxLen = max(maxLen,right-left);
}
return maxLen;
}
原文地址:https://blog.csdn.net/weixin_48144140/article/details/134540765
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_8541.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
