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