首页/新闻资讯/正文详情

LeetCode 1658.将 x 减到 0 的最小操作数:哈希表(+前缀和) / 滑动窗口

发布时间:2026/9/24 9:49:22 来源:云帆数科 栏目:资讯中心
LeetCode 1658.将 x 减到 0 的最小操作数:哈希表(+前缀和) / 滑动窗口
【LetMeFly】1658.将 x 减到 0 的最小操作数哈希表(前缀和) / 滑动窗口力扣题目链接https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/给你一个整数数组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(nums[0..i]) - i存入哈希表。倒序遍历一遍数组记录遍历过程中的后缀和c n t cntcnt。如果x − c n t x-cntx−cnt在哈希表中则找到一个可行的移除方法。时间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))空间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))AC代码C/* * LastEditTime: 2026-09-23 18:40:09 */classSolution{public:intminOperations(vectorintnums,intx){unordered_mapint,intprefix;for(inti0,cnt0,nnums.size();incntx;i){cntnums[i];prefix[cnt]i;}prefix[0]-1;intansprefix.count(x)?prefix[x]1:nums.size()1;for(intnnums.size(),in-1,cnt0;i0cntx;i--){cntnums[i];if(prefix.count(x-cnt)){ansmin(ans,prefix[x-cnt]n-i1);}}returnansnums.size()?-1:ans;}};解题方法二滑动窗口移除前后缀共计x xx即使得剩余数组和为s u m − x sum-xsum−x。滑动窗口每次右边加入窗口一元素当窗口中元素和大于s u m − x sum-xsum−x时不断移除左边元素。若移除结束后窗口中元素和等于s u m − x sum-xsum−x则更新答案。时间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))空间复杂度O ( 1 ) O(1)O(1)AC代码C/* * LastEditTime: 2026-09-23 18:48:44 */classSolution{public:intminOperations(vectorintnums,intx){intallValaccumulate(nums.begin(),nums.end(),0);xallVal-x;if(x0){// 不然while会下标越界return-1;}intans10000000;for(intl0,r0,nnums.size(),cnt0;rn;r){cntnums[r];while(cntx){cnt-nums[l];}if(cntx){ansmin(ans,n-(r-l1));}}returnans10000000?-1:ans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源

相关推荐

华为U2000网管验收实操:从设备管理到性能监控的六项测试要点
华为U2000网管验收实操:从设备管理到性能监控的六项测试要点

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:49:16

YOLOv11交通检测实战:轻量模型+车流统计+Modbus红绿灯控制
YOLOv11交通检测实战:轻量模型+车流统计+Modbus红绿灯控制

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:49:10

STM32开发环境搭建:ST-LINK驱动安装与Keil调试实战指南
STM32开发环境搭建:ST-LINK驱动安装与Keil调试实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:48:57

【轨物方案】AI 给建议,人拍板:我们做电力行业 Agent 的三条设计原则
【轨物方案】AI 给建议,人拍板:我们做电力行业 Agent 的三条设计原则

过去一年,“Agent”成了技术圈出现频率最高的词之一。但在电力、能源这类严肃行业里,真正的问题是:一个 AI 智能体要怎样设计,客户才敢把它放进生产流程?放在标书制作这样“错一个字都可能废标”的场景里,这… · 2026/9/24 10:32:42

平衡球机器人实战:OpenCV视觉定位与STM32级联PID控制
平衡球机器人实战:OpenCV视觉定位与STM32级联PID控制

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 10:32:42

STM32不掉电时钟方案:DS1302+纽扣电池实战记录
STM32不掉电时钟方案:DS1302+纽扣电池实战记录

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 10:28:58

Kornia 修复四元数奇点处 NaN/Inf 梯度:`quaternion_exp_to_log` 与 `euler_from_quaternion` 的边界防护实现解析
Kornia 修复四元数奇点处 NaN/Inf 梯度:`quaternion_exp_to_log` 与 `euler_from_quaternion` 的边界防护实现解析

计算机视觉人工智能深度学习图像处理 【免费下载链接】kornia 🐍 Geometric Computer Vision Library for Spatial AI 项目地址: https://gitcode.com/gh_mirrors/ko/kornia 点击查看 免费下载 导读 位姿优化与刚体运动学中,四元数对数和欧… · 2026/9/24 10:28:58

鸿蒙开发:ArrayList,可不会让UI更新哦
鸿蒙开发:ArrayList,可不会让UI更新哦

前言有同学遇到了一个问题&#xff0c;他是使用ArrayList来存储的数据&#xff0c;在动态给集合添加数据后&#xff0c;UI并未更新&#xff0c;代码如下&#xff1a;import { ArrayList } from kit.ArkTS;Entry Component struct Index {State numItems: ArrayList<string&g… · 2026/9/24 10:28:51

用NanoVNA调NFC天线匹配:从S11到读卡距离全面提升
用NanoVNA调NFC天线匹配:从S11到读卡距离全面提升

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 10:28:45

基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程
基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程

简介&#xff1a;这是一套面向计算机、人工智能、自动化等专业学生与教师的毕业设计级项目资源&#xff0c;围绕YOLOv8实现渔船作业监控系统&#xff0c;可用于毕设、课程设计、大作业或项目立项演示。压缩包共97个文件&#xff0c;约24.21MB&#xff0c;以70个Python源码文件为… · 2026/9/24 0:00:13

1D-CNN时间序列建模实战:从Conv1d原理到工业落地
1D-CNN时间序列建模实战:从Conv1d原理到工业落地

简介&#xff1a;面向时间序列数据建模的一维卷积神经网络完整实现&#xff0c;适合深度学习入门者及需要快速验证时序模型的研究者&#xff0c;能够从音频、文本、传感器或股价等序列中挖掘局部特征与时间依赖。压缩包体积很小&#xff0c;只有3KB&#xff0c;内含3个Python脚… · 2026/9/24 0:00:26

柔软的L:汉语语流中被忽视的舌肌张力控制
柔软的L:汉语语流中被忽视的舌肌张力控制

1. 这个“L”不是字母表里的L&#xff0c;而是舌尖上的L最近在几个方言群和语音教学社群里&#xff0c;反复看到有人发一句&#xff1a;“也说字母L&#xff1a;柔软的长舌”。初看以为是英语发音课笔记&#xff0c;点开才发现全是方言爱好者、播音系学生、语言康复师甚至戏曲演… · 2026/9/24 0:00:44

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码