LeetCode 热题 HOT 100：滑动窗口专题

LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/

3. 无重复字符的最长子串

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置的后一个才开始不重复
        Map<Character, Integer> map = new HashMap<>();
        int start = 0; // 滑动窗口的左指针
        int maxLen = 0; // 最大长度
        for(int end = 0; end < s.length(); end ++){
            char ch = s.charAt(end);
            if(map.containsKey(ch)){ // 如果当前元素与窗口中的元素重复，那么更新start。
                // 若遇到 abba 这种字符串，当遍历到第二个 b 时，start 指向第二个 b。
                // 继续遍历到 a 是，map 中 a 的 value 指向第一个 b， 因此需要比较大小
                start = Math.max(start, map.get(ch));
            }
            map.put(ch, end + 1); // 无论是否更新 start，都会更新其 map 数据结构和结果 maxLen
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }
}

128. 最长连续序列

题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) { // 先去重再排序
            set.add(nums[i]);
        }
        int co = 0;
        for (Integer num : set) {
            nums[co++] = num;
        }
        return sliderWindows(nums, set.size());
    }

    public int sliderWindows(int[] nums, int len){
        int start = 0;
        int max = 1;
        for (int end = 1; end < len; end ++) {
            if(nums[end] - nums[end-1] != 1){
                start = end; 
            }
            max = Math.max(max, end - start + 1);
        }
        return max;
    }
}

239. 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

通过优先队列模拟堆结构：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] arr = new int[len-k+1];
        // 优先队列采用大顶堆的结构：存储当前元素和下标索引
        PriorityQueue<int[]> heaps = new PriorityQueue<>((arr1, arr2) -> arr2[0]-arr1[0]);
        
        for(int i = 0; i < k; i ++){
            heaps.add(new int[]{nums[i], i}); // 尾部添加元素
        }
        
        int co = 0;
        arr[co++] = heaps.peek()[0];
        for(int i = k; i < len; i ++){
            heaps.add(new int[]{nums[i], i});
            while(heaps.peek()[1] <= i-k){ 
                // 当数组是 3,1,-1,4 时，滑动窗口大小为 3，当遍历到 4 时堆顶元素 4 已经失效
                // 更大的元素进队时，栈顶元素不用出队了，避免了频繁的出队
                // 当 4 也失效出堆，假设 3 是堆中的最大值，当 4 出堆时调整堆，3 变成堆顶，最终也会根据索引超出范围将 3 出堆。
                heaps.poll(); // 从堆顶出堆，并调整堆
            }
            arr[co++] = heaps.peek()[0];
        }
        return arr;
    }
}

438. 找到字符串中所有字母异位词

题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

分别设置比较串和待比较串的窗口，窗口为 26 个字母的出现的次数，遍历比较即可得出结果：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){ // 如果 p 的长度大于待比较的 s 长度，则不存在异位词
            return res;
        }
        int sLen = s.length();
        int pLen = p.length();
        int[] sWin = new int[26];
        int[] pWin = new int[26];

        for(int i = 0; i < pLen; i ++){
            sWin[s.charAt(i) - 'a']++;
            pWin[p.charAt(i) - 'a']++;
        }

        if(Arrays.equals(sWin, pWin)){
            res.add(0);
        }

        for(int i = pLen; i < sLen; i ++){
            sWin[s.charAt(i-pLen) - 'a'] --;
            sWin[s.charAt(i) - 'a'] ++;
            if(Arrays.equals(sWin, pWin)){
                res.add(i-pLen+1);
            }
        }
        return res;
    }
}