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

题目大意 #

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 。

解题思路 #

给定一个数组 nums 和一个整数 x，要求从数组两端分别移除一些数，使得这些数加起来正好等于整数 x，要求输出最小操作数。
要求输出最小操作数，即数组两头的数字个数最少，并且加起来和正好等于整数 x。由于在数组的两头，用 2 个指针分别操作不太方便。我当时解题的时候的思路是把它变成循环数组，这样两边的指针就在一个区间内了。利用滑动窗口找到一个最小的窗口，使得窗口内的累加和等于整数 k。这个方法可行，但是代码挺多的。
有没有更优美的方法呢？有的。要想两头的长度最少，也就是中间这段的长度最大。这样就转换成直接在数组上使用滑动窗口求解，累加和等于一个固定值的连续最长的子数组。
和这道题类似思路的题目，209，1040(循环数组)，325。强烈推荐这 3 题。

代码 #

package leetcode

func minOperations(nums []int, x int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	target := total - x
	if target < 0 {
		return -1
	}
	if target == 0 {
		return len(nums)
	}
	left, right, sum, res := 0, 0, 0, -1
	for right < len(nums) {
		if sum < target {
			sum += nums[right]
			right++
		}
		for sum >= target {
			if sum == target {
				res = max(res, right-left)
			}
			sum -= nums[left]
			left++
		}
	}
	if res == -1 {
		return -1
	}
	return len(nums) - res
}

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

⬅️上一页

下一页➡️