【C++习题】12.滑动窗口_将 x 减到 0 的最小操作数
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
- 图解
–
题目链接:
1658.将 x 减到 0 的最小操作数
题目描述:
解法
正难则反
转化为:找出最长的子数组的长度
len
,所有的元素的和刚好等于sum-x
left=0,right=0
进窗口,
sum±nums[right]
判断,
sum>target
出窗口,
sum-=nums[left]
更新结果,
sum==target
这里需要注意的是,若当right
指向c
的时候>target
,即right
指向c-1
的时候<target
。
此时left
往后移动一位,right
就不需要从头开始遍历了,因为left
指向1
的时候,right
从1~c-1
与b
之间的距离都是<target
的。
C++ 算法代码:
class Solution
{public:int minOperations(vector<int>& nums, int x) {int sum = 0;// 计算数组中所有元素的总和for(int a : nums) sum += a;int target = sum - x;// 计算目标值,即总和减去x// 细节问题if(target < 0) return -1;// 如果目标值小于0,说明无论如何操作都无法达到目标,返回-1int ret = -1;// 初始化结果为-1,表示尚未找到有效解// 使用滑动窗口技术来寻找最长的子数组,其和等于targetfor(int left = 0, right = 0, tmp = 0; right < nums.size(); right++){tmp += nums[right]; // 进窗口// 将当前元素加入临时和while(tmp > target) // 判断tmp -= nums[left++]; // 出窗口// 如果临时和大于目标值,则移动左指针以减少临时和if(tmp == target) // 更新结果// 如果临时和等于目标值,则更新结果ret = max(ret, right - left + 1);}if(ret == -1) return ret;// 如果没有找到有效的子数组,返回-1else return nums.size() - ret;// 否则,返回需要移除的元素数量,即数组长度减去最长子数组的长度}
};
图解
输入:nums = [1,1,4,2,3], x = 5
-
sum=1+1+4+2+3=11
target=sum-x=11-5=6
left = 0, right = 0, tmp = 0
循环两次后
tmp == target
ret = max(ret, right - left + 1)=3
-
right++,
tmp > target
tmp -= nums[left++];
tmp -= nums[left++];
-
tmp == target
ret = max(ret, right - left + 1)=3
后面步骤差不多,不过多赘述了。
-
return nums.size() - ret=5