滑动窗口算法学习

最近做了几道有关滑动窗口的算法，在此总结一下。

滑动窗口

• 就像描述的那样，可以理解成是一个会滑动的窗口，每次记录下窗口的状态，再找出符合条件的适合的窗口
• 可以使用滑动窗口来减少时间复杂度

经典滑动窗口题目

给一组大小为n的整数数组，计算长度为k的子数组的最大值
比如：数组{1,2,3,4,5,7,6,1,8},k=2，那么最终结果应该是7+6=13最大。
最简单的是使用两层遍历，通过所有情况找出最大的一个子数组，时间复杂度O(N^2)
使用滑动窗口，从[0,k-1]的一个窗口，记录其总和，然后窗口向右移动到[1,k],再到[2,k+1]，直到数组的最尾端，找出里面总和最大的一个窗口，这样的解法就是滑动窗口算法。

//Java代码：
public class SlidingWindow {
    public static int maxnum(int[] array,int k){
        if(array.length<k){//如果k比数组长度还大，返回-1
            return -1;
        }
        int left=0;
        int sum=0;
        for(int i=0;i<k;i++){
            sum+=array[i];
        }
        int tempsum=sum;//tempsum记录每个窗口的总和
        while (left+k<array.length){
            tempsum=tempsum-array[left]+array[left+k];
            left++;
            sum=Math.max(sum,tempsum);//sum取原sum和tempsum的较大值
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] arr={1, 4, 2, 10, 2, 3, 1, 0, 20};
        int k=3;
        System.out.println(maxnum(arr,k));
    }
}
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

字符串中的使用

• 问题描述：
  给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
  注意子串要与 words 中的单词完全匹配，中间不能有其他字符

public class Matching {

    public static List<Integer> findSubstring(String s,String[] words){
        List<Integer> res=new ArrayList<>();
        if(s==null||s.length()==0||words==null||words.length==0)
            return res;
        HashMap<String,Integer> map=new HashMap<>();//储存words字符数组，value值为出现的次数
        int word=words[0].length();//每个子串的长度
        int number=words.length;//子串的个数
        for(String w:words){
            map.put(w,map.getOrDefault(w,0)+1);//map中如果没有当前子串，则放入；如果有数目+1
        }
        for(int i=0;i<word;i++){
            int left=i,right=i,count=0;
            HashMap<String,Integer> temp=new HashMap<>();
            while (right+word<=s.length()){
                String match=s.substring(right,right+word);//滑动窗口
                right+=word;
                if(!map.containsKey(match)){
                    count=0;
                    left=right;
                    temp.clear();
                }
                else {
                    temp.put(match,temp.getOrDefault(match,0)+1);
                    count++;
                    while (temp.getOrDefault(match,0)>map.getOrDefault(match,0)){//如果匹配的个数多了，向右滑动word个字符
                        String match1=s.substring(left,left+word);
                        count--;
                        temp.put(match1,temp.getOrDefault(match1,0)-1);
                        left+=word;
                    }
                    if(count==number) res.add(left);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        System.out.println(findSubstring(s,words));
    }

}
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
46

• 问题描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
  输入: “abcabcbb”
  输出: 3

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //使用HashSet作为滑动窗口,找出无重复字符的最长子串。
        Set<Character> set=new HashSet<>();
        int ans=0,i=0,j=0;//i为滑动窗口的左边，j为右边
        while(i<s.length()&&j<s.length()){
            if(!set.contains(s.charAt(j))){//如果没有重复
                set.add(s.charAt(j++));
                ans=Math.max(ans,j-i);
            }
            else{//如果出现重复
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

用滑动窗口用来解决求字符串，数组等连续的子串或子数组的问题比较简单。