滑动窗口实例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 <= 105
  • 1 <= nums[i] <= 104
  • 1 <= 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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/115084.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

全套解决方案:基于pytorch、transformers的中文NLP训练框架,支持大模型训练和文本生成,快速上手,海量训练数据!

全套解决方案&#xff1a;基于pytorch、transformers的中文NLP训练框架&#xff0c;支持大模型训练和文本生成&#xff0c;快速上手&#xff0c;海量训练数据&#xff01; 1.简介 目标&#xff1a;基于pytorch、transformers做中文领域的nlp开箱即用的训练框架&#xff0c;提…

WebGPU加载Wavefront .OBJ模型文件

在开发布料模拟之前&#xff0c;我想使用 WebGPU 开发强大的代码基础。 这就是为什么我想从 Wavefront .OBJ 文件加载器开始渲染 3D 模型。 这样&#xff0c;我们可以快速渲染 3D 模型&#xff0c;并构建一个简单而强大的渲染引擎来完成此任务。 一旦我们有了扎实的基础&#x…

视频文件损坏无法播放如何修复?导致视频文件损坏的原因

如果我们遇到因视频文件损坏而无法正常播放&#xff0c;我们该怎么办&#xff1f;这种情况通常意味着视频文件已经损坏。我们不能访问、编辑或使用它们。那么应该用什么正确的工具和修复程序来修复视频呢&#xff1f; 视频文件损坏的原因 了解视频损坏如何修复之前&#xff0c…

【C51基础实验 LED流水灯】

51单片机项目基础篇 LED流水灯1、硬件电路设计和原理分析2、软件设计2.1、利用循环和移位操作符功能实现&#xff1a;LED流水灯2.2、利用利用封装好的库函数功能实现&#xff1a;LED流水灯 3、编译结果4、结束语 LED流水灯 前言&#xff1a; 前几篇学会了LED驱动原理&#xff…

Mysql001:Mysql概述以及安装

前言&#xff1a;本课程将从头学习Mysql&#xff0c;以我的工作经验来说&#xff0c;sql语句真的太重要的&#xff0c;现在互联网所有的一切都是建立在数据上&#xff0c;因为互联网的兴起&#xff0c;现在的数据日月增多&#xff0c;每年都以翻倍的形式增长&#xff0c;对于数…

数据库CPU飙高问题定位及解决

在业务服务提供能力的时候&#xff0c;常常会遇到CPU飙高的问题&#xff0c;遇到这类问题&#xff0c;大多不是数据库自身问题&#xff0c;都是因为使用不当导致&#xff0c;这里记录下业务服务如何定位数据库CPU飙高问题并给出常见的解决方案。 CPU 使用率飙升根因分析 在分…

概念解析 | 量子时代的灵感:探索量子感知技术

注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:量子感知技术。 量子时代的灵感:探索量子感知技术 量子感知技术是一个充满希望和挑战的新兴领域。在此,我们将深入探讨这个主题,概述其背景,解释其工作原理,讨论现有的…

mov怎么改成mp4?跟我一起操作吧

mov怎么改成mp4&#xff1f;mov因为并不是一种常见的视频文件格式&#xff0c;因此大家对这种视频文件可能知道的并不多&#xff0c;但如果你是用的是苹果手机&#xff0c;那么你会发现苹果手机拍摄的视频转移到电脑上后就是mov格式的&#xff0c;因为mov格式的视频并没有受到大…

JDBC使用了哪种设计模式

JDK中提供了操作数据库的接口&#xff0c;比如 java.sql.Driver java.sql.Connection java.sql.Statement java.sql.PreparedStatement 不同的数据库厂商提供操作自己数据库的驱动包&#xff0c; 比如mysql public class Driver extends NonRegisteringDriver implements jav…

一篇文章带你了解-selenium工作原理详解

前言 Selenium是一个用于Web应用程序自动化测试工具。Selenium测试直接运行在浏览器中&#xff0c;就像真正的用户在操作一样。支持的浏览器包括IE&#xff08;7, 8, 9, 10, 11&#xff09;&#xff0c;Mozilla Firefox&#xff0c;Safari&#xff0c;Google Chrome&#xff0c…

DC电源模块不同的尺寸可以适应实际应用场景

BOSHIDA DC电源模块不同的尺寸可以适应实际应用场景 DC电源模块是现代电子设备的必备部件之一&#xff0c;其可提供稳定的直流电源&#xff0c;保证电子设备正常运行。DC电源模块尺寸的选择直接影响到其适应的应用场景及其性能表现。本文将从尺寸方面分析DC电源模块的适应性&a…

【zookeeper】zookeeper介绍

分布式协调技术 在学习ZooKeeper之前需要先了解一种技术——分布式协调技术。那么什么是分布式协调技术&#xff1f;其实分布式协调技术主要用来解决分布式环境当中多个进程之间的同步控制&#xff0c;让他们有序的去访问某种临界资源&#xff0c;防止造成"脏数据"的…

C++ list模拟实现

list模拟实现代码&#xff1a; namespace djx {template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T,class Ref,class Pt…

Mac操作系统Safari 17全新升级:秋季推出全部特性

苹果的内置浏览器可能是Mac上最常用的应用程序&#xff08;是的&#xff0c;甚至比Finder、超级Mac Geeks还要多&#xff09;。因此&#xff0c;苹果总是为其浏览器Safari添加有用的新功能。在今年秋天与macOS Sonoma一起推出的第17版中&#xff0c;Safari可以帮助你提高工作效…

活用 命令行通配符

本文是对 阮一峰老师命令行通配符教程[1]的学习与记录 通配符早于正则表达式出现,可以看作是原始的正则表达式. 其功能没有正则那么强大灵活,而胜在简单和方便. - 字符 切回上一个路径/分支 如图: !! 代表上一个命令, 如图: [Linux中“!"的神奇用法](https://www.cnblogs.…

不会还有人排长队吃饭吧?用这招,快速搞定!

随着现代企业对员工福利和工作环境的关注不断增加&#xff0c;企业智慧食堂已经成为了企业管理的重要组成部分。 智慧收银系统的出现不仅使员工用餐变得更加便捷和高效&#xff0c;还提供了一种强大的管理工具&#xff0c;有助于企业更好地理解员工消费行为、优化食堂运营&…

比较器的工作原理及性能指标介绍

一、什么是比较器 比较器的功能是比较两个或更多数据项&#xff0c;以确定它们是否相等&#xff0c;或者确定它们之间的大小关系和排列顺序&#xff0c;这称为比较。可以实现此比较功能的电路或设备称为比较器。比较器是将模拟电压信号与参考电压进行比较的电路。比较器的两个…

说说Flink中的State

分析&回答 基本类型划分 在Flink中&#xff0c;按照基本类型&#xff0c;对State做了以下两类的划分&#xff1a; Keyed State&#xff0c;和Key有关的状态类型&#xff0c;它只能被基于KeyedStream之上的操作&#xff0c;方法所使用。我们可以从逻辑上理解这种状态是一…

掌握逻辑漏洞复现技术,保护您的数字环境

环境准备 这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 1、支付逻辑漏洞 攻击相关介绍 介绍&#xff1a; 支付逻辑漏洞是指攻击者利用支付系统的漏洞&#xff0c;突破系统的限制&#xff0c;完成非法的支付操作。攻击者可以采…

ZKP硬件加速

1. 引言 本文重点关注&#xff1a; 1&#xff09;何为硬件加速&#xff1f;为何需要硬件加速&#xff1f;2&#xff09;ZKP的关键计算原语&#xff1a; Multiscalar MultiplicationNumber Theoretic TransformationArithmetic Hashes 3&#xff09;所需的硬件资源4&#xff0…