分析公司网站的开发策略,上海网站制作全包,四川住房和城乡建设厅网站不能进入,广州流感最新情况题目链接#xff1a;**. - 力扣#xff08;LeetCode#xff09;**#xff08;字节跳动#xff09;
题目描述#xff1a;
给你一个整数数组 nums 和一个整数 x 。每一次操作时#xff0c;你应当移除数组 nums 最左边或最右边的元素#xff0c;然后从 x 中减去该元素的…题目链接**. - 力扣LeetCode**字节跳动
题目描述
给你一个整数数组 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 105 1 nums[i] 104 1 x 109
提示正难则反
解法滑动窗口
算法思路
题目要求的是数组「左端 右端」两段连续的和为 x 的最短数组信息量稍微多一些不易理清思路我们可以转化成求数组内一段连续的、和为 sum(nums) - x的最长数组。此时就是熟悉的「滑动窗口」问题了。
算法流程
a.转化问题求 target all - x 的 最长数组。如果targe 0,问题无解 b.初始化左右指针 left 0right 0滑动窗口区间表示为[left,right)左右区间是否开闭很重要必须设定与代码一致记录当前滑动窗口内数组和的变量 sum 0记录当前满足条件数组的最大区间长度 maxlen 0 c.当 right 小于等于数组长度时一直循环 1️⃣ 如果 sum target ,右移右指针直至变量和大于等于 target或右指针已经移到头 2️⃣ 如果 sum target ,右移左指针直至变量和小于等于 target或左指针已经移到头 3️⃣ 如果经过前两步的左右移动使得 sum target维护满足条件数组的最大长度并让下个元素进入窗口 d.循环结束后如果 ret 的值有意义则计算结果返回否则返回 -1。
class Solution {
public:int minOperations(vectorint nums, int x) {int n nums.size();int sum 0;int maxlen 0;int all 0;for(int i 0; i n; i){all nums[i];}int target all - x;//最长子数组目标值//处理细节if(target 0) return -1;if(target 0) return n;for(int left 0, right 0; right n; right){//进窗口sum nums[right];while(sum target){//判断sum - nums[left];//出窗口}//更新结果if(sum target){maxlen max(right - left 1, maxlen);}}int ret n - maxlen n ? -1 :n - maxlen;return ret;}
};
