滑动窗口实例4(将x减到0的最小操作数)
题目:
给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。
示例 1:
输入:nums = [1,1,4,2,3], x = 5 输出:2 解释:最佳解决方案是移除后两个元素,将 x 减到 0 。
示例 2:
输入:nums = [5,6,7,8,9], x = 4 输出:-1
示例 3:
输入:nums = [3,2,20,1,1,3], x = 10 输出:5 解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。
提示:
1 <= nums.length <= 1051 <= nums[i] <= 1041 <= x <= 109
算法原理:
正面入手解题,情况繁杂,一会是取左边一会是取右边,但是正难则反,反面入手解题:
题目要求可以转成:求最长一段连续的子数组区间,要求区间和为sum-x(sum是数组所有元素的和),那么最小操作数=数组所有元素个数-最长子数组长度
题目本来的要求是:求「左端+右端」两段连续的、和为 x 的最短数组

连续区间,可以考虑用滑动窗口来解题
1 求出数组所有元素的和sum 目标值target=sum-x
2 用滑动窗口,找出最长的子数组,使其和为target
细节:target可能为负数(当sum<x时)但是题目提示中所有元素均不存在负数
所以返回-1
left=0(左边界) right=0(指向待进入窗口的元素) sum2统计区间和
a 进窗口:sum2+=nums[right]
b 判断: 若是sum2>target 循环出窗口,直至sum<=target
若是循环结束后,sum2==target,则找到一组结果,若此次结果更优则更新结果
c 出窗口:sum-=nums[left],left++
代码实现:
class Solution
{
public:int minOperations(vector<int>& nums, int x){int sum = 0;for(auto e:nums){sum+=e;}int target = sum-x;if(target<0)//细节{return -1;}int left = 0;int right = 0;int n = nums.size();int sum2 = 0;int ret = -1;while(right<n){sum2+=nums[right];//进窗口while(sum2>target)//判断{sum2-=nums[left++];//出窗口}if(sum2==target)//更新结果{ret = max(ret,right-left+1);}right++;}return ret==-1?ret: n-ret;}
};相关文章:
滑动窗口实例4(将x减到0的最小操作数)
题目: 给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 ,返回 …...
数据库原理及应用(MySQL)
建议大屏观看,避免格式错误,影响观感 目录 第一章 数据库系统概述 1.数据库系统概述 1.1.信息 1.2.数据 1.3.信息和数据之间的联系 1.4.数据库(DB) 1.5.数据库管理系统(DBMS) 1.6.数据库管理系统的…...
初识Maven(一)命令行操作和idea创建maven工程
Maven 是 Apache 软件基金会组织维护的一款专门为 Java 项目提供**构建**和**依赖**管理支持的工具。 构建过程包含的主要的环节:- 清理:删除上一次构建的结果,为下一次构建做好准备 - 编译:Java 源程序编译成 *.class 字节码文件…...
MHA高可用配置及故障切换
1.什么是 MHA MHA(MasterHigh Availability)是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中,MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过…...
FPGA/IC秋招面试题 1(解析版)
分享个人觉得遇到还不错的题,后续有会继续补充。。。 以下题目均来自网络平台,用于学习交流如有侵权立马删除!!! 1. Verilog语言中,下面哪些语句不可被综合() A. #delay语句 B. initial语句 C. always语句 D. 用gen…...
华为云 异构数据迁移
数据库和应用迁移 UGO(Database and Application Migration UGO,以下简称为UGO)是专注于异构数据库结构迁移的专业服务。可将源数据库中的DDL、DML和DCL一键自动转换为华为云GaussDB/RDS的SQL语法,通过数据库评估、对象迁移两大核…...
wininet,winhttp,xmlhttprequest,各版本区别 《转》
一、标准API接口WinINet(Microsoft Windows Internet)和WinHTTP(Microsoft Windows HTTP) 实现Http访问,微软提供了二套API:WinINet, WinHTTP(分别封装于system32目录下的wininet.dll和winhttp.dll内) 二者主要区别在于后者更为安…...
朴素,word,任何参考文献导入endnote
朴素,word,任何参考文献导入endnote 注意:对于以下这几种不做阐述,看其他帖子都有讲述: 这里的参考文献指的是类似于: [1]. Li Y, Lu Y, Huo X, et al. Bandgap tuning strategy by cations and halide io…...
数学建模--三维图像绘制的Python实现
目录 1.绘制三维坐标轴的方法 2.绘制三维函数的样例1 3.绘制三维函数的样例2 4.绘制三维函数的样例3 5.绘制三维函数的样例4 6.绘制三维函数的样例5 1.绘制三维坐标轴的方法 #%% #1.绘制三维坐标轴的方法 from matplotlib import pyplot as plt from mpl_toolkits.mplot3…...
Spring Cloud Alibaba-Feign整合Sentinel
第1步: 引入sentinel的依赖 <!--sentinel客户端--> <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-sentinel</artifactId> </dependency> 第2步: 在配置文件中开启Feign对Sentinel的…...
zabbix配置钉钉告警、和故障自愈
钉钉告警python脚本 cat python20 #!/usr/bin/python3 #coding:utf-8 import requests,json,sys,os,datetime # 机器人的Webhook地址 webhook"钉钉" usersys.argv[1] textsys.argv[3] data{"msgtype": "text","text": {"conten…...
Web安全测试(五):XSS攻击—存储式XSS漏洞
一、前言 结合内部资料,与安全渗透部门同事合力整理的安全测试相关资料教程,全方位涵盖电商、支付、金融、网络、数据库等领域的安全测试,覆盖Web、APP、中间件、内外网、Linux、Windows多个平台。学完后一定能成为安全大佬! 全部文章请访问专栏:《全栈安全测试教程(0基…...
本地PC机通过SSH方式远程Jetson
1. 检测电脑是否安装openSSH 以管理员身份运行powershell终端输入以下命令: Get-WindowsCapability -Online | ? Name -like OpenSSH*若没有安装OpenSSH,会出现如下图提示: 输入Add-WindowsCapability -Online -Name OpenSSH.Client~~~~0.…...
面向对象 学习黑马视频(03)
1.内存分区模型 /* 面向对象编程** 内存分区模型* 1.代码区:存放函数体的二进制代码,由操作系统进行管理的* 2.全局区:存放全局变量和静态变量以及常量* 3.栈区:由编译器自动分配释放,存放函数的参数值…...
FinClip 支持创建 H5应用类小程序;PC 终端 优化升级
FinClip 的使命是使您能够通过小程序解决关键业务流程挑战,并完成数字化转型。不妨让我们看看本月产品与市场发布亮点,是否有助于您实现目标。 产品方面的相关动向👇👇👇 FinClip 支持创建 H5应用类小程序 近期我们…...
YOLOV8实例分割——详细记录环境配置、自定义数据处理到模型训练与部署
前言 Ultralytics YOLOv8是一种前沿的、最先进的(SOTA)模型,它在前代YOLO版本的成功基础上进行了进一步的创新,引入了全新的特性和改进,以进一步提升性能和灵活性。作为一个高速、精准且易于操作的设计,YO…...
2309ddocx02文档
风格,页眉和页脚等内容与主要分开,允许在起始文档中放大量自定义,然后在生成文档中显示. 打开文档 from docx import Document document Document() document.save("test.docx")真正打开文档 要用文件名打开文档: document Document("existing-document-f…...
第一章初识微服务
文章目录 认识微服务单体架构分布式架构需要考虑的问题 微服务微服务的具体架构微服务技术对比企业中的技术需求 总结 服务拆分注意事项 认识微服务 随着互联网行业的发展,对服务的要求也越来越高,服务架构也从单体架构逐渐演变为现在流行的微服务架构。…...
微信小程序电影票订票小程序软件设计与实现
摘 要 我们的生活水平正在不断的提高,然而提高的一个重要的侧面表现就是更加注重我们的娱乐生活。电影是我们都喜欢的一种娱乐方式,各式各样的电影给我们带来的喜悦也是大不相同的。带来快乐的同时也因为其复杂、繁琐的流程让电影爱好者们变得烦躁起来。…...
Redis 缓存预热+缓存雪崩+缓存击穿+缓存穿透
面试题: 缓存预热、雪萌、穿透、击穿分别是什么?你遇到过那几个情况?缓存预热你是怎么做的?如何造免或者减少缓存雪崩?穿透和击穿有什么区别?他两是一个意思还是载然不同?穿适和击穿你有什么解…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...
