优选算法:长度最小的子数组(滑动窗口)

embedded/2024/11/26 11:15:54/

        题目详情:. - 力扣(LeetCode) 

一. 题目解析

        题意为:给一个数组,找其中元素相加>=目标值的最小子数组(子数组是连续的)

二. 算法分析

        首先我们第一次看到这个题,第一想法肯定是暴力解法。既两个for循环暴力相加来判断,毫无疑问暴力解法肯定会超时,所以我们是算法正是基于暴力解法进行优化的

        首先,我们还是定义两个指针left right 进行搜索然后相加,然后比较。这听起来好像和暴力解法没区别吧? 接下来这个细节将是最大的区别

        如图,当left,right找到了大于等于目标值的情况,先记录长度。然后作为暴力解法的话就是,left++,right=left+1。这里的话仔细看我们会发现没必要,当大于等于目标和时,我们只需要移动left ,然后判断移动后的结果:如果仍是大于等于目标值,记录长度,left++。如果小于目标值则移动right,知道再次遇到大于目标和的情况再次进行判断

三. 代码实现

class Solution {
public://滑动窗口:利用单调性+两个同向指针(指针不回退)时使用滑动窗口int len = INT_MAX;int minSubArrayLen(int target, vector<int>& nums){int left = 0, right = 0;int sum = 0;for (; right < nums.size();right++){sum += nums[right];while (sum >= target){len = min(len, right - left + 1);sum -= nums[left++];}}return len == INT_MAX ? 0 : len;}
};


http://www.ppmy.cn/embedded/140603.html

相关文章

Unity3D 截图

使用 Unity3D 自带的截图接口&#xff0c;制作截图工具。 截图 有时候我们想对 Unity 的窗口进行截图&#xff0c;如果直接使用一些截图工具&#xff0c;很难截取到一张完整分辨率的图片&#xff08;例如&#xff0c;我们想要截取一张 1920 * 1080 的图片&#xff09;。 其实…

Spring 框架七大模块(Java EE 学习笔记03)

​ ​核心容器模块&#xff08;Core Container&#xff09; 核心容器模块在Spring的功能体系中起着支撑性作用&#xff0c;是其他模块的基石。核心容器层主要由Beans模块、Core模块、Contex模块和SpEL模块组成。 &#xff08;1&#xff09;Beans模块。它提供了BeanFactory类&…

微信小程序点击跳转打电话功能

wx.makePhoneCall 属性类型默认值必填说明phoneNumberstring是需要拨打的电话号码successfunction否接口调用成功的回调函数failfunction否接口调用失败的回调函数completefunction否接口调用结束的回调函数&#xff08;调用成功、失败都会执行&#xff09; <view class&q…

【C++11】尽显锋芒

(续) 一、可变参数模板 C11支持可变参数模板&#xff0c;也就是说支持可变数量参数的函数模板和类模板&#xff0c;可变数目的参数被称 为参数包&#xff0c;存在两种参数包&#xff1a;模板参数包&#xff0c;表示零或多个模板参数&#xff1b;函数参数包&#xff1a;表示零…

HTML5和CSS3新增特性

HTML5的新特性 HTML5新增的语义化标签 HTML5 的新增特性主要是针对于以前的不足&#xff0c;增加了一些新的标签、新的表单和新的表单属性等。 这些新特性都有兼容性问题&#xff0c;基本是 IE9 以上版本的浏览器才支持&#xff0c;如果不考虑兼容性问题&#xff0c;可以大量…

MySQL中的锁与优化SQL查询性能

MySQL作为一种高效、稳定、易用的开源关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;在大数据量和高并发的场景中&#xff0c;其性能优化显得尤为重要。锁机制和SQL查询优化是MySQL性能调优的两个关键方面。本文将详细探讨MySQL中的锁类型以及如何优化SQL查询…

【VUE3】VUE组合式(响应式)API常见语法

ref() //const count ref(0) //count.value&#xff08;访问值&#xff0c;包括对象要加.value&#xff09; //任何类型的值&#xff0c;包括深层嵌套的对象或则JS内置数据结构 await nextTick() //要等待 DOM 更新完成后再执行额外的代码&#xff0c;可以使用 nextTick() …

(免费送源码)计算机毕业设计原创定制:Java+SSM+JSP+Ajax+MySQLSSM国外鞋服代购平台

摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;鞋服代购平台当然也不例外。代购平台是以实际运用为开发背景&#xff0c;运用软件工程原理和开发方法&#xff0c;采用…