必要商城官网,搜索引擎优化包括哪些方面,wordpress 换图片地址,网站开发运营服务合同1.题目 2.算法思路
这个题目难在要转化一下才能用滑动窗口。
题意是需要在数组的前后两段区间进行解题#xff0c;但同时对两段区间进行操作是比较困难的#xff0c;我们可以将中间这段区间只和与nums_sum-x#xff08;数组总和-x#xff09;进行比较#xff0c;这样就可…1.题目 2.算法思路
这个题目难在要转化一下才能用滑动窗口。
题意是需要在数组的前后两段区间进行解题但同时对两段区间进行操作是比较困难的我们可以将中间这段区间只和与nums_sum-x数组总和-x进行比较这样就可以很好的将两段区间合并成一段区间进而使用滑动窗口算法解题。
滑动窗口算法我在《优选基础算法》中滑动窗口的前两个题目中介绍的比较清楚大家可以去看一看。
3.提交结果与代码实现 class Solution {
public:int minOperations(vectorint nums, int x) {int sum10,nnums.size(),sum20,len0;for(auto e:nums) sum1e;int targetsum1-x;//正难则反if(target0) return -1;//考虑边界情况if(target0) return n;//考虑边界情况for(int left-1,right0;rightn;right){sum2nums[right];//进窗口while(sum2target) sum2-nums[left];出窗口if(sum2target) lenmax(len,right-left);//更新结果}if(len0) return -1;else return nums.size()-len;}
};
时间复杂度O(n)。空间复杂度O(1)。
