4、长度最小的子数组

这篇具有很好参考价值的文章主要介绍了4、长度最小的子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        找到一个数组中,有多少个连续元素的和小于某个值,求出连续元素的长度的最小值。

滑动窗口法:

        其本质也是快慢指针,一个指针指向窗口的起始位置,另一个指针指向窗口的终止位置。

    1.定义快慢指针:

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

2.更新慢指针:

并记录长度

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

3. 更新快指针:

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

4.重复第二步:

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

一直到慢指针遍历到数组尾部。

但是以上更新快指针的方式是错误的。

伪代码如下:

i = 0;
result = MAX;
for(j = 0; j <= numsize; j++)
{
    sum += nums[i];
    while(sums >= s)
    {
        subl = j - i + 1;//subl值的是滑动窗口的长度
        result = min(subl,result);//更新最小的窗口长度
        //开始移动起始位置
        sums = sums - nums[i];
        i++;
    }
}

         注意,里面是while,原因如下:

          当有一种数组1,1,1,1.....1,100,values = 105,我们要滑动快指针的时候是一个一个滑动,看代码的意思。

第一次滑动到终止: 

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

再滑动快指针:

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构

4、长度最小的子数组,c语言,c++算法刷题笔记,数据结构文章来源地址https://www.toymoban.com/news/detail-632070.html

到了这里,关于4、长度最小的子数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(38)
  • [自我记录]随想录刷题第二天 | 977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

     代码随想录打卡第二天, 新手自我记录一下刷题历程, 仅为自我打卡使用. 今天刷了三道主题, 第一道双指针和第三道模拟做出来了, 第二道写出了暴力解法但是提交leetcode超时了, 测试用例过了18/20, 看了carl哥答案以后自己重新补写了滑动窗口方法. 977. 有序数组的平方 简单题

    2024年02月05日
    浏览(43)
  • 【算法专题突破】滑动窗口 - 长度最小的子数组(9)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:209. 长度最小的子数组 - 力扣(Leetcode)  要注意的是,题目给的是正整数, 而题目要求并不难理解,就是找最短的子数组。 如果使用暴力的话,就是一个O(N3)的算法,复杂度很高, 我们可以用滑动窗口来做,

    2024年02月09日
    浏览(30)
  • 算法-有序数组的平方,长度最小的子数组,螺旋矩阵II

    伪装成一个老手! 题目 给你一个按 非递减顺序 排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 : 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100] 来源:力扣977 思路 遍

    2024年02月11日
    浏览(41)
  • 算法练习-长度最小的子数组(思路+流程图+代码)

            难度:简单         分类:数组         难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。         给定一个含有个正整数的数组和一个正整数s,找出该数组中满足其和

    2024年01月18日
    浏览(41)
  • 两种解法解决LCR 008. 长度最小的子数组【C++】

    😄 创作不易,你的点赞和关注都是对我莫大的鼓励,再次感谢您的观看😄

    2024年02月07日
    浏览(34)
  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(40)
  • 【C++代码】有序数组的平方,长度最小的子数组,螺旋矩阵 II--代码随想录

    题目:有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums ,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 题解 数组其实是有序的, 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端, 不是最左边就是最右边,不

    2024年02月11日
    浏览(44)
  • 算法训练 Day 2 | 数组:977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

    977. 有序数组的平方 第一想法:暴力破解 看完题解想法:朝着双指针方向想 遇到困难: 用双指针的话,一开始想到两边指针往中间靠,逐个将最大值赋给结果数组。和题解不同的是,循环条件我写了  while (left != right) {...} ,相比于题解的  while (left = right) {...} ,我需要在后

    2023年04月12日
    浏览(41)
  • 4、长度最小的子数组

            找到一个数组中,有多少个连续元素的和小于某个值,求出连续元素的长度的最小值。         其本质也是快慢指针,一个指针指向窗口的起始位置,另一个指针指向窗口的终止位置。     1.定义快慢指针: 2.更新慢指针: 并记录长度 3. 更新快指针: 4.重复第二步

    2024年02月14日
    浏览(27)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包