创建一个网站的最常用的方法是先建立一个文件夹,二手手机回收网站开发,wordpress多语言无效,wordpress数字超市题目#xff1a;
给你一个整数数组 nums 和一个整数 x 。每一次操作时#xff0c;你应当移除数组 nums 最左边或最右边的元素#xff0c;然后从 x 中减去该元素的值。请注意#xff0c;需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 #xff0c;返回 …题目
给你一个整数数组 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-xsum是数组所有元素的和那么最小操作数数组所有元素个数-最长子数组长度
题目本来的要求是求「左端右端」两段连续的、和为 x 的最短数组 连续区间可以考虑用滑动窗口来解题
1 求出数组所有元素的和sum 目标值targetsum-x
2 用滑动窗口找出最长的子数组使其和为target 细节target可能为负数当sumx时但是题目提示中所有元素均不存在负数 所以返回-1 left0左边界 right0指向待进入窗口的元素 sum2统计区间和 a 进窗口sum2nums[right] b 判断 若是sum2target 循环出窗口直至sumtarget 若是循环结束后sum2target则找到一组结果若此次结果更优则更新结果 c 出窗口sum-nums[left]left
代码实现
class Solution
{
public:int minOperations(vectorint nums, int x){int sum 0;for(auto e:nums){sume;}int target sum-x;if(target0)//细节{return -1;}int left 0;int right 0;int n nums.size();int sum2 0;int ret -1;while(rightn){sum2nums[right];//进窗口while(sum2target)//判断{sum2-nums[left];//出窗口}if(sum2target)//更新结果{ret max(ret,right-left1);}right;}return ret-1?ret: n-ret;}
};
