leetcode-1658-Minimum-Operations-to-Reduce-X-to-Zero

发表于   |  

描述

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 is possible**, otherwise, return -1.

Example 1:

1
2
3
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:

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

Example 3:

1
2
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 <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

分析

这题可以转换为，找到一个最长的子序列，使得 x=sum(nums)-sum(nums[left:right])

滑动窗口问题，左右逼近即可。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        numsLen = len(nums)
        targetVal = sum(nums) - x
        
        if targetVal < 0:
            return -1
        if targetVal == 0:
            return numsLen
        
        left, right = 0, 0
        nowVal = 0
        result = 10**8
        
        while right < numsLen:
            nowVal += nums[right]
            while nowVal > targetVal:
                nowVal -= nums[left]
                left += 1
            if nowVal == targetVal:
                result = min(result, numsLen-(right-left+1))
            right += 1
        return -1 if result == 10**8 else result

解决方案2(Golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func minOperations(nums []int, x int) int {
    left, right := 0, 0
    result := 10000000000
    sum := 0
    
    for _, num := range nums {
        sum += num
    }
    if sum < x {
        return -1
    }
    
    targetVal := sum - x
    nowVal := 0
    
    for right < len(nums) {
        nowVal += nums[right]
        for nowVal > targetVal {
            nowVal -= nums[left]
            left += 1
        }
        if nowVal == targetVal {
            result = min(result, len(nums)-(right-left+1))
        }
        right += 1
    }
    if result == 10000000000 {
        return -1
    }
    return result
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

相关问题

题目来源