手机怎么制作网站网址,个人网站设计 优帮云,临河做网站,旅游景区网站模板1. 题目链接#xff1a;1658. 将 x 减到 0 的最小操作数
2. 题目描述: 给你一个整数数组 nums 和一个整数 x 。每一次操作时#xff0c;你应当移除数组 nums 最左边或最右边的元素#xff0c;然后从 x 中减去该元素的值。请注意#xff0c;需要 修改 数组以供接下来的操作…1. 题目链接1658. 将 x 减到 0 的最小操作数
2. 题目描述: 给你一个整数数组 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 3. 解法滑动窗口
3.1 算法思路
先计算出最长数组用总长度减去减去最长数组如果恰好减到0返回最小操作数否则返回-1
3.2 算法流程 转化问题求targetsum-x。如果target0,直接返回-1 当right小于数组长度时一直循环 如果tmptarget右移右指针直至变量和大于等于target或右指针已经移到了头 如果tmptarget右移左指针直至变量和大小等于target或左指针已经移到了头 如果经过前两步的左右移动使得tmptarget维护满足条件数组的最大长度并让下个元素进入窗口 循环结束后返回结果
class Solution {
public:int minOperations(vectorint nums, int x) {int sum0;int ret-1;int left0,right0;int tmp0;//计算所有元素的和for(int i0;inums.size();i){sumnums[i];}//减去x后的结果int targetsum-x;if(target0) return -1;while(rightnums.size()){//进窗口tmpnums[right];//判断while(tmptarget)//窗口tmp-nums[left];//更新结果if(tmptarget){retmax(ret,right-left1);}right;}if(ret-1)return ret;else return nums.size()-ret;}
};
