0%

LeetCode 1658. Minimum Operations to Reduce X to Zero

Posted on In

题目

原题在此

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

  • 1 <= nums.length <= $10^5$
  • 1 <= nums[i] <= $10^4$
  • 1 <= x <= $10^9$

解析

设sum =, n = nums.size(). 此时, 原题等价于求最长的subarray使得subarray的各项元素和等于sum - x.
用和这道题一样的滑动窗口思路求解即可.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        long long sum = -x;
        for(int num : nums)
            sum += num;
        int left = 0, right = 0, res = -1, n = nums.size();
        long long temp = 0; 
        while(left < n && right < n) {
            while(right < n && temp < sum) temp += nums[right++];
            res = (temp == sum) ? max(res, right - left) : res;
            do temp -= nums[left++]; while(left < n && temp > sum);
        }
        return res == -1 ? -1 : n - res;    
    }
};