滑动窗口
  TEZNKK3IfmPf 2023年11月14日 17 0
滑动窗口问题

先看一下题目和解决代码

 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}

滑动窗口问题和双指针有点像,不过华东窗口更多是确定一个范围值,像是一个窗口
步骤

  1. 确定窗口内是什么
  2. 如何移动结束为止
  3. 如何移动起始位置
【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: 类中执行顺序 下一篇: ios新游上架
  1. 分享:
最后一次编辑于 2023年11月14日 0

暂无评论

TEZNKK3IfmPf