滑动窗口问题
先看一下题目和解决代码
1public class MinSubArrayLen {
2 /**
3 * 209. 长度最小的子数组
4 * 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
5 * <p>
6 * <p>
7 * <p>
8 * 示例:
9 * <p>
10 * 输入:s = 7, nums = [2,3,1,2,4,3]
11 * 输出:2
12 * 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
13 * <p>
14 * <p>
15 * 进阶:
16 * <p>
17 * 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
18 *
19 * @param s
20 * @param nums
21 * @return
22 */
23 public static int minSubArrayLen(int s, int[] nums) {
24 int resultLength = Integer.MAX_VALUE;
25 int start = 0;
26 int sum = 0;
27 for (int end = 0; end < nums.length; end++) {
28 sum += nums[end];
29 while (sum >= s) {
30 int len = end - start + 1;
31 resultLength = resultLength < len ? resultLength : len;
32 sum -= nums[start++];
33 }
34 }
35 if (resultLength == Integer.MAX_VALUE) {
36 return 0;
37 } else {
38
39 return resultLength;
40 }
41 }
42}
滑动窗口问题和双指针有点像,不过华东窗口更多是确定一个范围值,像是一个窗口
步骤
- 确定窗口内是什么
- 如何移动结束为止
- 如何移动起始位置