每日一练【将 x 减到 0 的最小操作数】

一、题目描述

给你一个整数数组?nums?和一个整数?x?。每一次操作时，你应当移除数组?nums?最左边或最右边的元素，然后从?x?中减去该元素的值。请注意，需要?修改?数组以供接下来的操作使用。

如果可以将?x?恰好?减到?0?，返回?最小操作数?；否则，返回?-1?。

二、题目解析

当我们首先看到这一题时，正面去解决是非常困难，我们首先需要理解一个算法思想：正难则反。

我们反过来理解这一道题：

找出最长的子数组长度，所有元素的和正好等于sum - x.

这样转换之后，可以采用滑动窗口解决。

注意滑动窗口的思路一般是

1. 进窗口
2. 判断循环条件
3. 决定是否出窗口

看时机决定更新结果。

三、原码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(int i = 0;i<nums.size();i++)
        {
            sum += nums[i];
        }
        int target = sum-x;
        int max_len = 0;
        if(target < 0)
            return -1;
        if(target == 0)
            return nums.size();
        for(int right = 0,left = 0,ret = 0;right<nums.size();right++)
        {
            //进窗口
            ret +=nums[right];          
            //判断条件，出窗口
            while(ret > target)
            {
                ret -= nums[left++];
            }
            if(ret == target)
            {
                max_len = max(max_len,right - left + 1);
            }  
        }
        if(max_len)
            return nums.size() - max_len;
        else
            return -1;
    }
};