【双指针】滑动窗口经典例题 力扣

无重复的最长子串LC3 中等

题目链接

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

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

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

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int len = s.length();
        Map<Character,Integer> windows = new HashMap<>();//记录窗口中每个字符出现的次数
        int res = 0;
        while(right<=len-1){// 扩 
            char c = s.charAt(right);
            windows.put(c,windows.getOrDefault(c,0)+1);
            right++;
            while(windows.get(c)>1){// 缩
                char c2 = s.charAt(left);
                windows.put(c2,windows.getOrDefault(c2,0)-1);
                left++;
            }
            res = Math.max(res,right-left);// 更新
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

找到字符串中所有子母异位词LC438 中等

题目链接

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        HashMap<Character,Integer> window = new HashMap<>();// 窗口中的字母数量
        HashMap<Character,Integer> need = new HashMap<>();  // 所需各字母数量
        for(int i = 0; i < p.length();i++)
            need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0)+1);
        
        int l = 0; // 左指针
        int r = 0; // 右指针
        int len = s.length();
        int succSum = 0;
        while(r < len){// 扩
            char c1 = s.charAt(r);
            r++;
            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(need.get(c1))){ // 注意equal而不是==
                    succSum++;
                }
            }
            while(r-l > p.length()){// 缩

                char c2 = s.charAt(l);
                l++;
                if(need.containsKey(c2)){
                    if(window.get(c2).equals(need.get(c2))){// 注意equal而不是==
                        succSum--;
                    }
                    window.put(c2,window.getOrDefault(c2,0)-1);
                }
            }
            if(succSum == need.size()){
                result.add(l);
            }   

        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

字符串的排列LC567 中等

题目链接

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
 

提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
1
2
3
4
5
6
7
8
9
10
11
12
13

代码：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0,right = 0;
        int s1len = s1.length();
        int s2len = s2.length();
        int vaild = 0;
        HashMap<Character,Integer> window = new HashMap<>();
        HashMap<Character,Integer> need = new HashMap<>();

        for(int i = 0; i < s1len;i++){
            char c = s1.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }

        while(right<s2len){
            char c1 = s2.charAt(right);
            right++;

            if(need.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1).equals(need.get(c1))){
                    vaild++;
                }
            }
            while(right-left > s1len){
                char c2 = s2.charAt(left);
                left++;
                if(need.containsKey(c2)){
                    if(window.getOrDefault(c2,0).equals(need.get(c2))){
                        vaild--;
                    }
                    window.put(c2,window.getOrDefault(c2,0)-1);
                }
            }
            if(vaild==need.size())return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

滑动窗口的最大值LC239 困难

题目链接

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：
输入：nums = [1], k = 1
输出：[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码：
单调队列：思路链接Labuladong

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {


        List<Integer> re = new ArrayList<>();
        Windows windows = new Windows();
        for(int i = 0; i < nums.length; i++){
            if(i<k-1){
                windows.push(nums[i]);
            }else{
                windows.push(nums[i]);
                re.add(windows.getMax());
                windows.pop(nums[i-k+1]);     
            }
        }
        int[] rearr = new int[re.size()];
		for (int i = 0; i < re.size(); i++) {
			rearr[i] = re.get(i);
		}
		return rearr;

    }
}

class Windows{
    // 单调队列，始终满足从大到小顺序，队尾放入元素时，删除前面比自己小的元素
    LinkedList<Integer> list = new LinkedList<>();

    void push(int a){ // 队尾放入元素时，删除前面比自己小的元素
        while(!list.isEmpty() && a > list.getLast()){
            list.removeLast();
        }
        list.addLast(a);
    }

    void pop(int i){ // 删除的元素刚好是第一个（最大元素）时，才真正触发删除
        if(list.getFirst()==i){
            list.removeFirst();
        }
    }

    int getMax(){
        return list.getFirst();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

参考：https://labuladong.github.io/algo/di-ling-zh-bfe1b/wo-xie-le–f02cd/