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

2023-12-13 20:38:30

一、题目描述

给你一个整数数组?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;
    }
};

文章来源:https://blog.csdn.net/hanwangyyds/article/details/134978582
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。