【算法】滑动窗口——将x减到0的最小操作数

本节博客主要是讲的我解“将x减到0的最小操作数”这道题的思路历程，从最开始的想法到代码提交的详细记录，有需要借鉴即可。

1.题目

题目链接：LINK

看题目意思是就是给你一个数X，让你拿着数组中的最左边或者最右边的数字与这个数字抵消(相减)，直到X为0，或者找不到，如果可以抵消掉，记录拿这个数组中最少的一个数字个数，而且用数组中的值的时候，必须用两头的。

这个暴力求解…都不知道下一次是用左边的数字还是右边的数字，…，基本暴力解法就想不到了。

这里我们老师讲的，说要用到转换思想——“正难则反”
什么意思呢？
其实对于这个题目来说，整个数组可以分为三块，即下图：

说白了就让我们找left + right这两块中最小的数字个数
那可以等效于让我们找 该数组总数字个数 - mind最大数字个数

顺着前面“滑动窗口”的代码思路：
大体就可以写出下面代码：

2.代码示例

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}long long target = ALsum - x;//中间的目标值，满足目标值就进行更新结果int ret = -1;//代表两边的长度，取最小值int len = 0;//代表left和right之间的长度，取最大值long long sum = 0;//代表中间区间的和//处理特殊情况if (sum == target){return n;}for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target && left < right){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};

这个题做完之后感觉还是有一两个坑的，下面进行展示：

3.细节

3.1left越界

这个问题呢，也可以说是X > 整个数组之和，即target小于0，导致了left会不断右移的情况：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}int target = ALsum - x;//中间的目标值，满足目标值就进行更新结果int ret = -1;//代表两边的长度，取最小值int len = 0;//代表left和right之间的长度，取最大值int sum = 0;//代表中间区间的和for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};

这个主要是越界问题，是left越界了。

3.2特殊情况

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ALsum = 0;int n = nums.size();for(size_t i = 0;i<n;i++){ALsum+=nums[i];}int target = ALsum - x;//中间的目标值，满足目标值就进行更新结果int ret = -1;//代表两边的长度，取最小值int len = 0;//代表left和right之间的长度，取最大值int sum = 0;//代表中间区间的和for(int right = 0,left = 0; right < n; right++){//进窗口sum+=nums[right];//出窗口while(sum > target && left < right){sum-=nums[left];left++;}//更新结果if(sum == target){len = max(len,right - left + 1);}}return ret = len == 0 ? -1 : n - len;}
};

这个是出了什么问题呢？就是这是一种数组里的数字全部都与X相消才行，特殊情况吧算是，需要特别处理一下。
我写的这个代码刚好默认是mid组至少有一个数字的，用我写的代码肯定是找不到的，所以需要特殊判断一下。

4.总结

感觉这个题关键是刚上来的转换思想很关键(怪不得是中等题目)，其次是想到滑动窗口，这俩细节问题的话可以通过调试调出来。

---

EOF