当前位置: 首页> 健康> 养生 > LeetCode Medium|【3. 无重复字符的最长子串】

LeetCode Medium|【3. 无重复字符的最长子串】

时间:2025/7/19 10:50:18来源:https://blog.csdn.net/caiziming_001/article/details/140888044 浏览次数:0次

力扣题目链接
状态:在本题中,我们可以很明显得看出出现了关键字:子串、最长,所以我们肯定是选用滑动窗口来解决这个题目。
滑动窗口首先要解决的就是我们选择什么样的容器来存储数据呢?本体中是计算重复字符,我们可以使用 set、map、数组均可以解决,这里分别给出三种方法。

set

这个非常直观,和我们做的一些滑动窗口的基础题是一样的

class Solution {
public:int lengthOfLongestSubstring(string s) {std::unordered_set<char> set;int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];while (set.find(rChar) != set.end()) {set.erase(s[left]);left++;}set.insert(rChar);ans = max(ans, right - left + 1);right++;}return ans;}
};

map

对于 map ,我们最需要搞清楚的就是 key 和 value ,这里我们的 key 肯定是字符,然后 value 肯定是对应的下标,因为我们的 map 只能去搜索 key。

这样的话我们就不需要内层循环了,可以直接更新 left 。如何更新呢?当然就是把重复字符排除在外,但是为了防止 left 的回退,所以我们有:

left = max(left, map[rChar] + 1);

这样的代码。

class Solution {
public:int lengthOfLongestSubstring(string s) {std::unordered_map<char, int> map;int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];if (map.find(rChar) != map.end()) {left = max(left, map[rChar] + 1);}map[rChar] = right;ans = max(ans, right - left + 1);right++;}return ans;}
};

数组

对于数组,解法和 map 其实非常类似。
我们第一反应肯定就是 26 个英文字母,但是由于我们题目中要求了 「s由英文、数字、符号和空格组成」,所以很自然的想法就是 255 来表示 ASCII 码。

同样的,我们在数组中存储的是对应的下标位置。

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> index(256, -1);int left = 0, right = 0;int ans = 0;while (right < s.length()) {char rChar = s[right];if (index[rChar] != -1 && index[rChar] >= left) {left = max(left, index[rChar] + 1);}index[rChar] = right; //还是隐式类型转换ans = max(ans, right - left + 1);right++;}return ans;}
};
关键字:LeetCode Medium|【3. 无重复字符的最长子串】

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: