题外话

今天开始刷 LeetCode 探索频道, 字节跳动的题目，一道字符串相关的经典题目，无重复最长子串. 明明记得做过, 然而写完暴力法，在尝试进行时间复杂度优化时，怎么也想不起来思路，竟然想用dp去解决。

所以发现一个问题，做过的题目，不总结不复习，掌握不牢固。 所以打算把有关 此题目的 滑动窗口 类的题目，今天做一个总结整理, 团灭滑动窗口问题.

​ 截屏2020-06-18下午3.02.00

滑动窗口

什么是滑动窗口？

  • 其实就是一个队列,比如 无重复的最长子串 例题中的 abcabcbb，进入这个队列**（窗口）**为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

  • 如何移动？

  • 我们只要把队列的左边的元素移出就行了，直到满足题目要求

  • 一直维持这样的队列，找出队列出现最长的长度时候，求出解

题目

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

这道题，跟题外话中头条那道题一模一样.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

示例 1:

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

思路一 ： 暴力法

  • 暴力法非常简单
  • 两层暴力循环找出每一种可能性，找出最大值
  • 这里我们不细说，直接上代码
 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

/**
 *
 * 暴力法
 * 两层循环
 *
 * 外层的 i 是以 i开头的字符串的无重复最长子串
 *
 * 依次往后比较，以每个字符开头的无重复子串的最长长度
 *
 * 时间复杂度 : O(N ^ 2)
 * 空间复杂度 : O(N)
 *
 * */
public static int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    int max = 1;
    HashSet<Character> set = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        set.clear();
        set.add(s.charAt(i));
        for (int j = i + 1; j < s.length(); j++) {
            if (set.contains(s.charAt(j))){
                max = Math.max(max, set.size());
                break;
            }else {
                set.add(s.charAt(j));
                max = Math.max(max, set.size());
            }
        }
    }
    return max;
}

思路二： 滑动窗口

算法执行过程，代码中有很明确的注释说明。下图为手动推导过程

WechatIMG248

 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

/**
 *
 * 上述方法时间复杂度为 O(N ^ 2)
 * 算法提交后，虽然ac了。但是执行耗时特别长。
 * 下边我们来做一下，时间复杂度的优化
 *
 * 滑动窗口
 * [left right] 分别为窗口的 开始位置和结束位置
 * 所以，当前窗口的元素个数就是 right - left
 * */

// 思路是逐步计算 以 第一个字符开头的最长无重复子串，第二个字符开头的...直到末尾
public static int lengthOfLongestSubstring1(String s) {
    if (s == null || s.length() == 0) return 0;
    if (s.length() == 1) return 1;

    // set用来记录窗口中，的元素
    Set set = new HashSet();
    // set中添加 /
    set.add(s.charAt(0));

    // 初始化窗口 left=0, right=1相当于 窗口中只有一个 a
    int res = 1,left = 0, right = 1;

    // 循环遍历条件 窗口最右侧到达 字符串最右端
    while (right < s.length()){
        // 窗口中元素 不包含 right指向的元素
        if (!set.contains(s.charAt(right))){
            // set中添加 right指向的元素
            set.add(s.charAt(right));
            // 计算当前窗口的值
            res = Math.max(res,right - left + 1);

            // 窗口右侧范围扩大
            right ++;
        }else {
            // 窗口元素中包含 right指向的元素
            // 窗口右移 -> 直到不包含right指向元素
            set.remove(s.charAt(left++));
        }
    }
    return res;
}

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

思路一 : 暴力破解

  • 从第 0 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
  • 从第 1 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度.
  • 从第 2 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
  • …
  • 从最后个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
  • 从上边得到的长度中选择最小的即可。
  • 时间复杂度 : O(N ^ 2)
  • 空间复杂度 : O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int start = i;
        int sum = 0;
        while (start < n) {
            sum += nums[start];
            start++;
            //当前和大于等于 s 的时候结束
            if (sum >= s) {
                min = Math.min(min, start - i);
                break;
            }
        }
    }
    //min 是否更新，如果没有更新说明数组所有的数字和小于 s, 没有满足条件的解, 返回 0
    return min == Integer.MAX_VALUE ? 0 : min;
}

思路二：滑动窗口

WechatIMG249

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    // sum 存放窗口中 数值总和
    // left 为窗口最左边
    // right 为窗口右边第一个元素
    // res 存放最终结果
    int sum = nums[0], left = 0, right = 1, res = Integer.MAX_VALUE;
    while (right < nums.length || left < nums.length){
        if (sum < s){
            // 当 sum < s时， 窗口向右扩大
            if (right == nums.length)
                sum -= nums[left ++];
            else
                sum += nums[right++];
        }else {
            // 当 sum >= s时，计算 res 
            // 左边窗口缩小
            res = Math.min(res, right - left);
            sum -= nums[left ++];
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

截屏2020-06-18下午6.09.12

239. 滑动窗口最大值

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

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

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

输入: 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sliding-window-maximum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

整体思路，利用双端队列,队列中存放下标, 对头存放最大值的下标，新进来一个元素，从队尾开始while循环比较，当比队尾元素大时，移除队尾元素，当队列为空，或者找到队列中元素比当前元素大时结束循环，并将当前元素插入队尾。

当队列对头存放的下标，不在滑动窗口范围即 < begain时，队头元素出队列

当下标有效即下标 >= 0 时， 开始拿出队列头部元素放入 maxes结果数组中.

经过一遍循环，时间复杂度O(n) 需要额外k个元素大小的双端队列，空间复杂度O(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
26
27
28
29
30
31
32
33
34
35


public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 1) return null;
    if (k == 1) return nums;

    // 存放滑动窗口最大值数组
    int[] maxes = new int[nums.length - k + 1];

    // 双端队列 存放数组的下标
    Deque<Integer> queue = new LinkedList();
    for (int i = 0; i < nums.length; i++) {

        // 循环从尾部开始比较，比尾部元素小时，移除尾部元素
        while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
            queue.removeLast();
        }

        // 讲当前元素加入队尾（也有可能是队头，当前元素比之前对头元素还大时）
        queue.addLast(i);

        // begain 就是结果元素的下标
        int begain = i - k + 1;

        // 取出对头元素，即最大值下标，当下标无效（ < begain） 时，将其移除
        if (queue.peekFirst() < begain){
            queue.removeFirst();
        }

        // begain有效，即>=0时，赋值
        if (begain >= 0){
            maxes[begain] = nums[queue.peekFirst()];
        }
    }
    return maxes;
}

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9 输出：[[2,3,4],[4,5]] 示例 2：

输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  • 滑动窗口
  • left 为 窗口的最左端， right外第一个元素
  • sum 为窗口中元素的总和
  • 初始化窗口 1
    • 此时 left为1， right为2， sum 为1
  • 从2开始遍历元素，知道 right < target
    • 当 sum == target时
      • 将窗口中的元素，添加到结果数组
      • 窗口左边 右移
    • 当 sum < target时
      • 窗口右边 右移
      • 并且 sum += right++
    • 当 sum > target时
      • 窗口左边 右移
      • 并且 sum -= left++
  • 遍历完毕后， 所有可能的结果就求出来了。
 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

/**
 *
 * 滑动窗口
 * left为窗口最左端， right为窗口右边第一个元素
 * sum 为 窗口中元素的总和
 * 初始化窗口 数组中 第一个元素
 * 
 * */
public static int[][] findContinuousSequence(int target) {

    List<int []> res = new ArrayList<>();

    int left = 1, right = 2, sum = 1;
    while (right <= target){
        if ( sum == target){
            // 添加滑动窗口中的元素
            // 窗口左边 右移
            int [] list = new int[right - left];
            for (int i = left; i < right; i++) {
                list[i] = i;
            }
            sum -= left ++;
            res.add(list);
        }else if (sum < target){
            // 窗口右边 右移
            sum += right ++;
        }else {
            sum -= left ++;
        }
    }

    int[][] ans = res.toArray(new int[res.size()][]);
    return ans;
}

优化：

循环遍历条件的优化

  • 当left >= target » 1时， 加上随意一个 右边的元素，结果都 > target
  • 所以，while循环结束条件，我们可以优化为
  • while (right < target && (left <= target » 1))

截屏2020-06-20下午11.07.33