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

今天药忘吃喽~ 2023-10-15 15:37 39阅读 0赞

LeetCode 热题 HOT 100：[https://leetcode.cn/problem-list/2cktkvj/][https_leetcode.cn_problem-list_2cktkvj]

--------------------

#### 文章目录 ####

*   *  3. 无重复字符的最长子串
     *  128. 最长连续序列
     *  239. 滑动窗口最大值
     *  438. 找到字符串中所有字母异位词

--------------------

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

题目链接：[https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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][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][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][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;
        }
    }

[https_leetcode.cn_problem-list_2cktkvj]: https://leetcode.cn/problem-list/2cktkvj/
[https_leetcode.cn_problems_longest-substring-without-repeating-characters_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_longest-consecutive-sequence_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/longest-consecutive-sequence/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_sliding-window-maximum_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/sliding-window-maximum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_find-all-anagrams-in-a-string_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj