滑动窗口问题

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 1 个元素，则它将变为 [i+1, j+1)（左闭，右开）。

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

• 暴力法

• • 比较暴力的方法，嵌套两次循环，时间复杂度为O(n^2)，具体思路为：使用一个双端队列，保存遍历到当前字符时不重复的字符串，下一个字符如果存在于队列中，则遍历到下一个字符时的子串长度为两个重复字符之间的距离，否则为上一个不重复子串长度加1

  本方法适用于记录每一个不重复子串的求解，不适用于仅需要最长子串长度的求解

public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        LinkedList<Character> queue = new LinkedList<>();
        queue.offer(s.charAt(0));
        int index = 1;
        int max = 1;
        while (index < s.length()){
            char temp = s.charAt(index);
            int s1 = isInQueue(queue, temp);
            if (s1 >= max){
                max = s1;
            }
            index ++;
        }
        return max;
    }
    
    // 返回队列中与目标字符相同字符的距离，即遍历到当前字符时最长不重复长度
    private int isInQueue(LinkedList<Character> queue, char c){
        LinkedList<Character> queueT = new LinkedList<>();
        int flag = 0;
        while (!queue.isEmpty()){
            if (queue.peekLast()!=c){
                queueT.offer(queue.pollLast());
                flag ++;
            } else{
                while(!queue.isEmpty()){
                    queue.poll();
                }
            }
        }
        while (!queueT.isEmpty()){
            queue.offer(queueT.pollLast());
        }
        queue.offer(c);
        return flag + 1;
}

• 使用hash表记录不重复子串的字符，可分别使用Set和Map or char[256]字符数组
• • 使用Set， 时间复杂度为O(2n) —> O(n)，通过使用 hash表作为滑动窗口，检查当前字符是否在不重复子串中仅需O(1)的时间，当前使用 HashSet 将字符存储在当前窗口[i, j)）中。 然后向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动j。直到s[j]已经存在于 HashSet 中。此时，找到的没有重复字符的最长子字符串将会以索引 i开头。当对所有的 i 这样做，就可以得到答案。

public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        Set<Character> set = new HashSet<>();
        int i = 0, j = 0, max = 0;
        while(i <= j && j < s.length()){
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                max = Math.max(max, j - i);
            } else {
                set.remove(s.charAt(i ++));
            }
        }
        return max;
}

• • 使用HashMap，时间复杂度为O(n)定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当找到重复的字符时，可以立即跳过该窗口，也就是说，如果 s[j]在 [i, j)有与j'的字符，我们不需要逐渐增加i以直接跳过[i，j']，并将j' + 1。

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
}

• • 使用char数组代替HashMap，时间复杂度为O(n)，将会节省一定的空间，具体思路同HashMap

public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; 
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
}

问题：有一个整形数组arr和一个大小为k的窗口从数组最左边滑动到最右边，窗口每次滑动一个位置，返回每个窗口内的最大值组成的数组

总结