长度最小的子数组 (LeetCode 209)

简介: 长度最小的子数组 (LeetCode 209)

长度最小的子数组 (LeetCode 209)

Description

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

Sample Input 1

target = 7, nums = [2,3,1,2,4,3]

Sample Output 1

2

Sample Input 2

target = 4, nums = [1,4,4]

Sample Output 2

1

Sample Input 3

target = 11, nums = [1,1,1,1,1,1,1,1]

Sample Output 3

0

算法思想:

暴力破解法:

这道题目暴力解法当然是 两个for循环,然后不断的寻找符合条件的子序列,时间复杂度很明显是O(n^2)。

代码如下:

int minSubArrayLen(int target, int* nums, int numsSize){
    //初始化最小长度为INT_MAX
    int minLength = INT_MAX;
    int sum;

    int left, right;
    for(left = 0; left < numsSize; ++left) {
        //每次遍历都清零sum,计算当前位置后和>=target的子数组的长度
        sum = 0;
        //从left开始,sum中添加元素
        for(right = left; right < numsSize; ++right) {
            sum += nums[right];
            //若加入当前元素后,和大于target,则更新minLength
            if(sum >= target) {
                int subLength = right - left + 1;
                minLength = minLength < subLength ? minLength : subLength;
            }
        }
    }
    //若minLength不为INT_MAX,则返回minLnegth
    return minLength == INT_MAX ? 0 : minLength;
}

滑动窗口法:

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

while(sum >= target) {
    int subLength = right - left + 1;
    minLength = minLength < subLength ? minLength : subLength;
    sum -= nums[left++];
}

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

代码如下:

int minSubArrayLen(int target, int* nums, int numsSize){
    //初始化最小长度为INT_MAX
    int minLength = INT_MAX;
    int sum = 0;

    int left = 0, right = 0;
    //右边界向右扩展
    for(; right < numsSize; ++right) {
        sum += nums[right];
        //当sum的值大于等于target时,保存长度,并且收缩左边界
        while(sum >= target) {
            int subLength = right - left + 1;
            minLength = minLength < subLength ? minLength : subLength;
            sum -= nums[left++];
        }
    }
    //若minLength不为INT_MAX,则返回minLnegth
    return minLength == INT_MAX ? 0 : minLength;
}

java代码如下:

class Solution {

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

$$ Created by Ss1Two on 2023/2/8 $$

目录
相关文章
|
9月前
flutter开发中Use ‘const’ with the constructor to improve performance. Try adding the ‘const’ keyword to the constructor invocation.报错如何解决-优雅草卓伊凡
flutter开发中Use ‘const’ with the constructor to improve performance. Try adding the ‘const’ keyword to the constructor invocation.报错如何解决-优雅草卓伊凡
116 1
|
消息中间件 C# RocketMQ
MQ产品使用合集之设置rocketmq的timerMaxDelaySec时间出现报错如何解决
消息队列(MQ)是一种用于异步通信和解耦的应用程序间消息传递的服务,广泛应用于分布式系统中。针对不同的MQ产品,如阿里云的RocketMQ、RabbitMQ等,它们在实现上述场景时可能会有不同的特性和优势,比如RocketMQ强调高吞吐量、低延迟和高可用性,适合大规模分布式系统;而RabbitMQ则以其灵活的路由规则和丰富的协议支持受到青睐。下面是一些常见的消息队列MQ产品的使用场景合集,这些场景涵盖了多种行业和业务需求。
755 4
|
存储 安全 Ubuntu
部署在CentOS上,有什么优缺点
【8月更文挑战第25天】部署在CentOS上,有什么优缺点
386 1
|
存储 缓存 NoSQL
Java中的内存数据库与缓存技术
Java中的内存数据库与缓存技术
element UI实现输入建议下拉列表 —— el-select filterable可筛选的下拉列表 or 带输入建议的输入框 el-autocomplete ?
element UI实现输入建议下拉列表 —— el-select filterable可筛选的下拉列表 or 带输入建议的输入框 el-autocomplete ?
675 0
|
SQL 安全 应用服务中间件
技术心得记录:弱口令漏洞详解
技术心得记录:弱口令漏洞详解
|
存储 缓存 Linux
嵌入式Linux中内存管理详解分析
嵌入式Linux中内存管理详解分析
230 0
|
网络协议 网络安全 网络架构
数据通信网络之IPv6静态路由
数据通信网络之IPv6静态路由
244 1
|
数据安全/隐私保护 iOS开发 MacOS
CocosCreator3.8研究笔记(二十四)CocosCreator 动画系统-动画编辑器实操-关键帧实现动态水印动画效果(2)
CocosCreator3.8研究笔记(二十四)CocosCreator 动画系统-动画编辑器实操-关键帧实现动态水印动画效果
235 0
|
监控 Linux
通过msr-tools读取CPU寄存器的值
通过msr-tools工具包可以用来来读取或写MSR寄存器值。 MSR是Model Specific Register的全称。 MSR是为了设置CPU 的工作环境和标示CPU 的工作状态,包括温度控制,性能监控等     1.
7419 0