剑指offer 48：最长不重复子串

题目描述：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解法一：滑动窗口

思路：

        首先，left和right同时指向窗口头部，右窗口不断右移动，用Set维护一个不重复的滑动窗口，当遇到重复元素，即刻移动左窗口，去重，同时记录此时窗空口的长度。然后重复前述步骤，直到窗口遍历完全部元素。

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Set<Character> set = new HashSet<>();
        for(int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            while(set.contains(c)) {
                set.remove(s.charAt(l++));
            }
            set.add(c);
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

解法二：双端队列

思路：

        用一个双端队列当成滑动窗口，当遇到队列中已经存在的数，就从队头开始删(直到删除这个存在的数)，否则就从队尾添加元素

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        int max=0;
        for (int i = 0; i < s.length(); i++) {
            if (!deque.contains(s.charAt(i))) {
                deque.addLast(s.charAt(i));
            }else {
                max = Math.max(max, deque.size());
                while(deque.peekFirst()!=s.charAt(i)) {
                    deque.removeFirst();
                }
                deque.removeFirst();
                deque.addLast(s.charAt(i));
            }
        }
        max = Math.max(max, deque.size());
        return max;
    }
}