算法通关村-----滑动窗口高频问题

无重复字符的最长子串

问题描述

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

问题分析

可以通过滑动窗口中的可变窗口思想来解决。设置两个指针，初始时left指向字符串的起始位置，right指向left的下一个位置。设置一个map,key是遍历到的字符，value是字符的下标，right不断向右移动，直到遇到重复字符或者遍历到字符串末尾。遇到重复字符后，记录长度，设置left为重复字符的下一个字符，继续遍历。直至right遍历到字符串末尾。详见leetcode3

代码实现

public int lengthOfLongestSubstring(String s) {
    if(s.length()==0||s.length()==1){
        return s.length();
    }
    Map<Character,Integer> map = new HashMap<Character,Integer>();
    int left=0;
    int right=1;
    int res=1;
    map.put(s.charAt(left),left);
    while(right<s.length()){
        if(map.containsKey(s.charAt(right))){
            left = Math.max(map.get(s.charAt(right))+1,left);
        }
        map.put(s.charAt(right),right);
        right++;
        if(right-left>res){
            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

长度最小的子数组

问题描述

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。详见leetcode209

问题分析

这是一道可变窗口问题，目的是找到最小窗口，使窗口内数据大于或者等于target。我们可以首先将left指针放在数组起始处，不断移动right指针，使窗口内数据相加大于等于target，之后可以移动left指针，直至窗口内数据之和小于target,在不断移动right指针，重复这个过程，记录下每一个满足条件的窗口大小，直至right指针移向数组末尾。返回可变窗口最小值。

代码实现

public int minSubArrayLen(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    int left=0;
    int right=0;
    int sum=0;
    while(right<nums.length){
        sum += nums[right++];
        while(sum>=target){
            minLen = Math.min(minLen,right-left);
            sum-=nums[left++];
        }
    }
    if(minLen==Integer.MAX_VALUE){
        return 0;
    }else{
        return minLen;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

盛水最多的容器

问题描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。详见leetcode11

问题分析

这是一个可变窗口问题。初始时，我们可以设置两个指针left和right指向数组0和n-1的位置，储水量为Math.min(height[right],hight[left])*(right-left),这就是短板效应。之后我们考虑两个指针向内移动，right-left一定会减小，当移动高度较大的指针时，高度也会变小，所以，我们只能移动高度小的指针。

代码实现

public int maxArea(int[] height) {
    if(height.length==0||height.length==1){
        return 0;
    }
    int left = 0;
    int right = height.length-1;
    int waterNum = 0;
    while(left<right){
        int num = Math.min(height[right],height[left])*(right-left);
        waterNum = Math.max(num,waterNum);
        if(height[right]>height[left]){
            left++;
        }else{
            right--;
        }
    }
    return waterNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

字符串的排列

问题描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。s1 和 s2 仅包含小写字母。详见leetcode567

问题分析，这是一个固定窗口问题。固定窗口大小为s1的长度，大小为s1长度的窗口在s2滑动，统计每个窗口中的字母种类和数量与s1是否一致，一致返回true，不一致继续扫描，直至right指针指向字符床末尾，还未扫描到，返回false。

public boolean checkInclusion(String s1, String s2) {
    int[] chars1 = new int[26];
    int[] chars2 = new int[26];
    int n = s1.length();
    int left = 0;
    int right = n-1;
    for(int i=0;i<n;i++){
        int index = s1.charAt(i)-'a';
        chars1[index]++;
    }
    while(right<s2.length()){
        for(int i=left;i<=right;i++){
            int index = s2.charAt(i)-'a';
            chars2[index]++;
        }
        if(Arrays.equals(chars1,chars2)){
            return true;
        }else{
            left++;
            right++;
            for(int i=0;i<26;i++){
                chars2[i] = 0;
            }
        }
    }
    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