网易企业邮箱是什么,昆明关键词优化软件,搭建电子商务平台,网页布局排版题目#xff1a; 无重复字符的最长子串
描述#xff1a; 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 leetcode链接 方法…题目 无重复字符的最长子串
描述 给定一个字符串 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(n1){//字符串只有一个元素那么最长无重复子串长度也为1return 1;}int left 0,right 1;int maxLen 0;while(rightn){int i left;//在子串中查找相同的元素while(s[right]!s[i]iright){i;}if(iright){//没有相同的元素则加入子串中right;}else{left i1;right i2;}//更新最大的子串长度maxLen max(maxLen,right-left);}return maxLen;
}方法二滑动窗口哈希表判断重重复元素 对于方法一中我们判断重复元素需要遍历一遍子数组时间复杂度为o(n),因此我们考虑用哈希表来优化查找重复元素的时间我们把子数组的每一个元素存储到哈希表中哈希表查找的时间复杂度为o(1)同样的我们定义两个指针left和rightleft 指向子数组的起始位置right指向待加入的元素然后我们利用count判断right指向的元素是否在子数组中存在如果不存在那么加入哈希表中如果存在删除哈希表中键为s[left]的元素然后left右移动循环此操作直到right指向的元素在子数组中不出现为止最后维护最大的子数组长度。 时间复杂度onleftright指针均只会向右移动遍历一遍字符串时间复杂度为on 空间复杂度on哈希表的空间为on int lengthOfLongestSubstring(string s) {int n s.size();int left 0,right 0;int maxLen 0;unordered_mapchar,int map;while(rightn){while(leftrightmap.count(s[right])){//删除有重复字符的子串直至不出现重复的字符map.erase(s[left]);}//把right指向的元素当成关键字插入mapmap[s[right]] 0;maxLen max(maxLen,right-left);}return maxLen;}
