大家好，我是一只编程熊，今天是LeetCode每日一题的第三天，学习的是LeetCode第三题《无重复字符的最长子串》。
题意
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
题解
观察样例，我们可以发现，依次递增地枚举子串的起始位置，那么合法的结束为止一定是递增的，因为对于起始位置 i-1 ，假设其不含有重复字符的最远右位置 j；那么对于起始位置为 i 的子串，因为 [i-1，j] 不含有重复字符，其不含有重复字符的最远右位置一定大于等于 i，因此我们考虑使用滑动窗口来解决本题。
滑动窗口本质上是利用了实现了双指针，利用了指针移动的单调性，不断移动找到合法的区间，其中包含了最长的区间。
本题中，我们可以固定右指针，找到最远的不含有重复字符的左指针，根据上面我们观察得到的性质可以，不含有重复字符的左指针是非递减的。
代码具体实现上我们可以用 queue 模拟双指针，辅助数组 cnt 统计窗口内每个字符出现的次数 ，来判断窗口是否有重复的字符。
时间复杂度:
空间复杂度:
知识点总结: 滑动窗口
C++代码
class Solution {
public:
queue<char> q;
int lengthOfLongestSubstring(string s) {
vector<char> cnt(128, 0);
int ans = 0;
for (int i = 0; i < int(s.size()); i++) {
q.push(s[i]), cnt[s[i]]++;
while (cnt[s[i]] > 1) {
char frontC = q.front();
q.pop();
cnt[frontC]--;
}
ans = max(ans, int(q.size()));
}
return ans;
}
};
Java代码
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] cnt = new char[128];
LinkedList<Character> q = new LinkedList<Character>();
int ans = 0;
for (int i = 0; i < s.length(); i++) {
q.add(s.charAt(i));
cnt[s.charAt(i)]++;
while (cnt[s.charAt(i)] > 1) {
char frontC = q.pollFirst();
cnt[frontC]--;
}
ans = Math.max(ans, q.size());
}
return ans;
}
}
题目链接: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
我是编程熊，持续输出 LeetCode题解、大厂面试、大厂靠谱点对点内推 相关内容，关注''一只编程熊"，获取信息。
欢迎 『关注』、『点赞』、『转发』支持~
