[LeetCode] 1658. Minimum Operations to Reduce X to Zero

 轉自LeetCode

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:

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

Solution

這題可以用 sliding window 來解，但需要換個思路

因為題目規定只能從最左或最右來移除數字，並且這些被移除數字的總和等於 x

因此，可以想成，留下來的數字的總和，等於全部的總和減掉x

所以可以變成找，總和為 totalSum - x 的最大 subarray

最後的答案就會是 nums.size - subarray.size

kotlin

	class Solution {
	fun minOperations(nums: IntArray, x: Int): Int {
	val totalSum = nums.fold(0) { total, item -> total + item}
	val target = totalSum - x
	when {
	target < 0 -> return -1
	target == 0 -> return nums.size
	}
	var sum = 0
	var left = 0
	var windowSize = -1
	for(right in nums.indices) {
	sum += nums[right]
	while(sum > target) {
	sum -= nums[left]
	++left
	}
	if(sum == target) {
	windowSize = Math.max(windowSize, right - left + 1)
	}
	}
	return if (windowSize == -1) -1 else nums.size - windowSize
	}
	}

view raw minimum_operations_to_reduce_x_to_zero.kt hosted with ❤ by GitHub