酒店网站建设公司,酷站网站,小说网站自动采集,网站规划的基本原则文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 和一个整数 x 。每一次操作时#xff0c;你应当移除数组 nums 最左边或最右边的元素#xff0c;然后从 x 中减去该元素的值。请注意#xff0c;需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 你应当移除数组 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 10^5
1 nums[i] 10^4
1 x 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
哈希记录前缀和及其长度遍历后缀和 tailsum在前缀和中查找 x-tailsum
class Solution {
public:int minOperations(vectorint nums, int x) {int n nums.size(), sum 0;unordered_mapint,int presum;presum[0] 0;//前缀和为0时长度为0for(int i 0; i n; i) {sum nums[i];presum[sum] i1;//前缀和对应的长度}int tailsum 0, minlen INT_MAX;if(presum.find(x) ! presum.end())minlen presum[x];for(int i n-1; i 0; i--){tailsum nums[i];int target x - tailsum;if(presum.find(target) ! presum.end() presum[target] i){minlen min(minlen, presum[target]n-i);}}return minlenINT_MAX ? -1 : minlen;}
};1088 ms 164.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
