算法第七天:leetcode之209.长度最小的子数组

一、长度最小的子数组

    209.长度最小的子数组的链接:https://leetcode.cn/problems/minimum-size-subarray-sum/

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

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

  示例 1:

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

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

 示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

  提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

  进阶:

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

  双指针滑动窗口的基础知识如下链接所示,感兴趣的读者可以点击或者复制该链接进行查阅和学习:

 https://mp.csdn.net/mp_blog/creation/editor/139633714

   本题使用滑动窗口的算法知识解题,以下是部分c++代码(省略力扣给出的代码块内容):

        int sum=0, i=0;
        int l=0;
        int result=INT32_MAX;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=target){
                l=j-i+1;
                result=min(result, l);
                sum=sum-nums[i];
                i++;
            }
        }
        return result==INT32_MAX ? 0 : result;

二、长度最小的子数组的基本思路

  1.  定义起始位置i,和终止位置j,然后不断调节子序列的起始位置和终止位置,定义一个最大值result去查找通过不断调节找最小的子数组;
  2. 用for循环查找,先求滑动窗口的数值之和,在和目标值target比较;
  3. 为什么用while循环?因为要一直循环查找,而且还要判断条件,所以用while循环比较好。取子序列的长度i,然后去找最小的子数组,sum=sum-num[i++],通过更新i的值,从而去不断变更初始位置i;
  4. 最后如果result没有被赋值,则返回0,说明没有符合条件的子序列。如果被赋值,则返回result。

 三、结言

    感谢各位读者的阅读与支持,您的支持是我前进的动力!我希望我的博文能够带给您有用的滑动窗口算法知识和启发。如果您有任何问题或意见,请随时联系我或在评论区评论。希望本题的算法知识对大家有帮助,我会一直持续更新算法知识的博客哦,谢谢各位读者的支持!!!

相关推荐

  1. 算法leetcode209.长度数组

    2024-06-17 08:56:02       7 阅读
  2. leetCode209.长度数组

    2024-06-17 08:56:02       20 阅读
  3. Leetcode 209. 长度数组

    2024-06-17 08:56:02       14 阅读
  4. leetcode209--长度数组

    2024-06-17 08:56:02       14 阅读
  5. 209.长度数组

    2024-06-17 08:56:02       37 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-17 08:56:02       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-06-17 08:56:02       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-06-17 08:56:02       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-06-17 08:56:02       18 阅读

热门阅读

  1. leetcode198 打家劫舍

    2024-06-17 08:56:02       8 阅读
  2. 结构型模式-享元模式

    2024-06-17 08:56:02       7 阅读
  3. CMake Tutorial (3.30-rc3版) 练习和点评

    2024-06-17 08:56:02       8 阅读
  4. HTML中的<br>、<hr>和<pre>标签使用指南

    2024-06-17 08:56:02       8 阅读
  5. 重庆思庄技术分享——启动Oracle下最小追踪日志

    2024-06-17 08:56:02       7 阅读
  6. vue实现图片预览

    2024-06-17 08:56:02       6 阅读
  7. 「C系列」C 文件读写

    2024-06-17 08:56:02       7 阅读
  8. 后端开发面试题4(附答案)

    2024-06-17 08:56:02       7 阅读
  9. C++ 二分查找法【面试】

    2024-06-17 08:56:02       7 阅读
  10. 1、C++编程中的基本运算 - 课件

    2024-06-17 08:56:02       7 阅读
  11. SpringSecurity(JWT、SecurityConfig、Redis)

    2024-06-17 08:56:02       6 阅读
  12. API 类别 - 特效核心

    2024-06-17 08:56:02       5 阅读
  13. Linux 基础IO 三

    2024-06-17 08:56:02       6 阅读
  14. 你应该知道的口语连读技巧

    2024-06-17 08:56:02       6 阅读
  15. Rust创建基准测试bench

    2024-06-17 08:56:02       6 阅读
  16. AWS无服务器 应用程序开发—第十三章 小结2

    2024-06-17 08:56:02       5 阅读
  17. 迁移学习和从头训练(from scratch)的区别

    2024-06-17 08:56:02       6 阅读