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和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源

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

相关推荐

ASP.NET Core 产品目录应用实战：在 SQL Server 2016/Azure SQL Database 中融合 JSON、时态表、数据脱敏与行级安全

RK3588本地部署DeepSeek大模型：Ollama与RKLLM NPU加速实战

马赫-曾德尔调制器π/2偏置控制：从半波电压到闭环稳定实战

更多资讯

SAP销售BOM配置与订单展开实战：从CS01到VA01的避坑指南

Ubuntu+IGH开源主站调试零差云控伺服电机全攻略

1850元X99平台实战：18核E5编译Android 12性能测试

基于STM32与OpenCV的平衡球PID控制实战：从视觉感知到增量式PID整定

立创EDA实测：自动布线与布局辅助功能全解析

Win11下HC05蓝牙模块配对失败的根源与COM端口解决方案

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？