无重复字符的最长子串
无重复字符的最长子串
问题描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
思路：
第一种思路，就是暴力出奇迹。
计算出s的长度。从字串开始的位置凑够第一个元素i=0开始，接下来的字串的第二个元素为第一个元素的后一个j=i+1，判断这个元素在之前有没有出现过，如果没有出现过，将无重复字符的最长子串的长度num++,j++，否则，字串开始的位置向后移动i++。
题解：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int Length = s.size();
int location = 0;
if (Length == 0) {
return 0;
} else {
int maxnum = 1;
for (int i = 0; i < Length; i++) {
int num = 1;
int flag = 0;
for (int j = i + 1; j < Length; j++) {
for (int m = i; m < j; m++) {
if (s[m] == s[j]) {
flag = 1;
}
}
if (flag == 1)
break;
num++;
}
if (num > maxnum) {
maxnum = num;
}
}
return maxnum;
}
}
};思路：
用的滑动窗口，详情见上一篇文章对滑动窗口的介绍。
设置一个大小为128的数组，因为ASCII只有128个，将他们的初始状态置为false，表示还没有出现过。
对于每一个在s中的字符来说，如果他的状态为false，那么将其push到队列中，并将其状态置为true；如果出现了，那么将队列中的所有元素弹出来，并将其状态置为false，然后将元素push到队列中。
最后要得到的答案为在push与pop过程中，队列的最大长度。
题解：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
bool in_queue[128] = {};
queue<char> que;
for (const char &each : s) {
while (in_queue[each]) {
in_queue[que.front()] = false;
que.pop();
}
que.push(each);
in_queue[each] = true;
ans = max(ans, int(que.size()));
}
return ans;
}
};