【C++习题】12.滑动窗口_将 x 减到 0 的最小操作数

–

题目链接：

1658.将 x 减到 0 的最小操作数

---

题目描述：

---

解法

正难则反

转化为：找出最长的子数组的长度len，所有的元素的和刚好等于sum-x

1. left=0，right=0

2. 进窗口，sum±nums[right]

3. 判断，sum>target

   出窗口，sum-=nums[left]

4. 更新结果，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

1. 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

2. right++，

   tmp > target

   tmp -= nums[left++];

   

   tmp -= nums[left++];

   

3. tmp == target

   ret = max(ret, right - left + 1)=3

   后面步骤差不多，不过多赘述了。

4. return nums.size() - ret=5