刷题笔记 day9

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

         解析：1. 当数组的两端的数都大于x时，直接返回 -1。

        2. 当数组所有数之和小于 x 时 ，直接返回 -1。

        3. 数组中可以将 x 消除为0，那么可以从左边减小为 0 ；可以从右边减小为 0 ； 也可以同时从左边和右边减小为 0 。

        这样分析下来，这道题的第三种情况的处理会比较麻烦，因为减小为 0 的区间存在不连续。

        但是子区间之和 等于 总区间和 - x 的这个子区间是连续的，简言之，target = sum -x ，sum等于原数组所有数之和。将该问题转化到 求最大长度和为target的连续子数组。

        算法原理：使用双指针 left 和 right ；

        利用变量ret 记录子区间的和，当ret > target 时，更新ret值，并将右移left指针；

        更新和为target的区间长度；

        最后返回 数组总长度 - 和为target 区间长度。

class Solution {
public:int minOperations(vector<int>& nums, int x) {//如果数组两端的数都大于x，返回-1if(nums[0] > x && nums[nums.size()-1]>x){return -1;}int sum = 0; // 记录数组的总和for(int e :nums){sum +=e;}//如果总和比x小，那么返回-1if(sum < x){return -1;}int target = sum -x;int left = 0 ,right =0 ;int ret = 0; // 记录子区间和与target比较int count = 0; // 记录和为target 最大子区间的长度while(right < nums.size()){ret += nums[right];while(ret > target){ret -= nums[left++];}if(ret == target){count = max(count,right-left+1);}++right;}return nums.size()-count;}
};