无重复字符的最长子串

问题描述：

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 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;
    }
};