算法学习（5）：LeetCode刷题之滑动窗口_滑动窗口的时间复杂度

前言：

滑动窗口算法专门优化一种连续问题场景，如找出字符串或者数组中满足xx条件的最长（或最短）的连续子串（或子数组）。

滑动窗口的解题思路如下：
需要用到双指针进行求解，两个指针构造一个窗口，窗口的移动是重点！
右指针每次往前移动一格，每次移动会有一个新的元素进入窗口，这时条件可能就会发生变化，再根据当前条件来决定左指针是否移动，以及移动多少格。总的来说，右指针每次必然要移动一格，目的是要探索“可能性”；左指针要随着移动，目的是要确定这次探索的“正确性”。滑动窗口的时间复杂度是O（n），因为2个指针分别遍历一次数组。

滑动窗口一般有3种类型：
1、固定窗口大小；
2、窗口大小不固定，求解最大能满足条件的窗口；
3、窗口大小不固定，求解最小能满足条件的窗口；
但是不管是哪种类型，基本的思路都是一样的，不一样的仅仅是代码的细节。

固定窗口大小的模板比较简单：

public int slidingWindowTemplate(String[] a, ...) {
    // 输入参数有效性判断
    if (...) {
        ...
    }

    // 申请一个散列，用于记录窗口中具体元素的个数情况
    // 这里用数组的形式呈现，也可以考虑其他数据结构，如Set，Map等
    int[] hash = new int[...];

    // 预处理(可省), 一般情况是改变 hash
    ...

    // l 表示左指针，r 表示右指针，如果是固定窗口，也可以只使用一个变量i来控制窗口大小
    // count 记录当前的条件，具体根据题目要求来定义
    // result 用来存放结果
    int l = 0, r = 0, count = ..., result = ...;
    for (int i = 0; i < ...; i++) {
    	// 先找到窗口的后边界
    }
    
	for (int i = 右边界; i < ...; i++) {
    	// 再依次滑动窗口，判断是否满足条件
    	if (条件满足) {
			// 更新结果
			results = ...
		}
    }

    return results;
}
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

不固定窗口大小，代码模板如下：

public int slidingWindowTemplate(String[] a, ...) {
    // 输入参数有效性判断
    if (...) {
        ...
    }

    // 申请一个散列，用于记录窗口中具体元素的个数情况
    // 这里用数组的形式呈现，也可以考虑其他数据结构，如Set，Map等
    int[] hash = new int[...];

    // 预处理(可省), 一般情况是改变 hash
    ...

    // l 表示左指针，r 表示右指针
    // count 记录当前的条件，具体根据题目要求来定义
    // result 用来存放结果
    int l = 0, r = 0, count = ..., result = ...;
    while (r < A.length) {
        // 更新新元素在散列中的数量
        hash[A[r]]--;

        // 根据窗口的变更结果来改变条件值
        if (hash[A[r]] == ...) {
            count++;
        }

        // 如果当前条件不满足，移动左指针直至条件满足为止
        while (count > K || ...) {
            ...
            if (...) {
                count--;
            }
            hash[A[l]]++;
            l++;
        }

        // 更新结果
        results = ...
    }

    return results;
}
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

正文

1、LeetCode 438. 找到字符串中所有字母的异位词

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

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

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
1
2
3
4
5
6
7
8
9
10
11

这是一道固定窗口大小的滑动窗口题，窗口的大小就是字符串p的长度。我们先构造好窗口，再把窗口一点一点往右滑动，滑动的过程中判断条件是否成立。代码如下：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        List<Integer> ans = new ArrayList<>();
        if (sl < pl) {
            return ans;
        }
		// 由于题目中说明了字符串只包含小写字母，所以可以使用数组进行字母计数
        int[] sArr = new int[26];
        int[] pArr = new int[26];
        // 先构造出初始化的窗口
        for (int i = 0; i < pl; i++) {
            sArr[s.charAt(i) - 'a']++;
            pArr[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sArr, pArr)) {
            ans.add(0);
        }
		// 再一点一点滑动窗口，注意判断满足的条件
        for (int i = pl; i < sl; i++) {
            sArr[s.charAt(i) - 'a']++;
            sArr[s.charAt(i - pl) - 'a']--;
            if (Arrays.equals(sArr, pArr)) {
                ans.add(i - pl + 1);
            }
        }
        return ans;
    }
}
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

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

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

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

这是一道窗口大小变化的滑动窗口题，先移动右指针，每次将窗口里增加一个元素，增加后，再判断是否满足条件，不满足的话，移动左指针，直到满足条件。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;

        int ans = 0;
        // 题目要求无重复的元素，可以使用Set结构进行存储
        Set<Character> set = new HashSet<>();
        // 移动右指针
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 如果不再满足条件，移动左指针，直到条件再次满足
            // 滑动窗口题目最重要的点就是要找到满足窗口的条件
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(c);
            // 更新结果
            ans = Math.max(ans, set.size());
        }
        return ans;
    }
}

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

3、LeetCode 1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。

示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释： 
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
1
2
3
4
5
6
7
8

如果这道题没有说可以从0变成1，那么将非常简单，如果加了这个条件，难点在于不知道要将哪些0变成1，如果使用枚举，复杂度将非常大。这道题同样可以使用滑动窗口，限定条件就是窗口内的0的个数不能多于K个。

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;

        int ans = 0;
        int total = k;
        // 移动右指针
        while (right < nums.length) {
        	// 移动过程中统计0的个数
            if (nums[right] == 0) {
                total--;
            }
            right++;
            // 如果不再满足条件，即窗口中0的个数多于K个了，就要移动左指针，
            while (total < 0) {
                if (nums[left] == 0) {
                    total++;
                }
                left++;
            }
            // 更新结果
            ans = Math.max(ans, right - left);
        }
        return ans;
    }
}
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

4、LeetCode 209. 长度最小的子数组

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1
2
3
4
5
6
7

这道题跟上面2题不同，这题是求满足条件的最短的子数组，其实套路是一样的，右指针先移动，然后计算窗口内元素的和，然后判断和是否大于target，在条件满足的情况下，尽可能的移动右指针，这样才能找到最小的间隔，代码如下：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;

        int ret = Integer.MAX_VALUE;
        int tmpSum = 0;
        // 右移指针
        while (right < nums.length) {
        	// 累加窗口内元素之和
            tmpSum += nums[right];
            right++;
            // 在满足条件的情况下，尽可能收缩窗口
            while (tmpSum >= target) {
                ret = Math.min(ret, right - left);
                tmpSum -= nums[left];
                left++;
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22