class Solution {
public:
int minOperations(vector<int>& nums, int x) {
}
};
1658. 将 x 减到 0 的最小操作数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4 输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10 输出：5 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1041 <= x <= 109原站题解
javascript 解法, 执行用时: 84 ms, 内存消耗: 52.6 MB, 提交时间: 2023-01-07 10:08:36
/**
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
var minOperations = function(nums, x) {
const n = nums.length;
const sum = _.sum(nums);
if (sum < x) {
return -1;
}
let right = 0;
let lsum = 0, rsum = sum;
let ans = n + 1;
for (let left = -1; left < n; ++left) {
if (left != -1) {
lsum += nums[left];
}
while (right < n && lsum + rsum > x) {
rsum -= nums[right];
++right;
}
if (lsum + rsum === x) {
ans = Math.min(ans, (left + 1) + (n - right));
}
}
return ans > n ? -1 : ans;
};
golang 解法, 执行用时: 116 ms, 内存消耗: 8.2 MB, 提交时间: 2023-01-07 10:07:30
func minOperations(nums []int, x int) int {
n := len(nums)
sum := 0
for _, num := range nums {
sum += num
}
if sum < x {
return -1
}
right := 0
lsum := 0
rsum := sum
ans := n + 1
for left := -1; left < n; left++ {
if left != -1 {
lsum += nums[left]
}
for right < n && lsum+rsum > x {
rsum -= nums[right]
right++
}
if lsum+rsum == x {
ans = min(ans, (left+1)+(n-right))
}
}
if ans > n {
return -1
}
return ans
}
func min(a, b int) int {
if b < a {
return b
}
return a
}
python3 解法, 执行用时: 312 ms, 内存消耗: 25.1 MB, 提交时间: 2023-01-07 10:06:33
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
n = len(nums)
total = sum(nums)
if total < x:
return -1
right = 0
lsum, rsum = 0, total
ans = n + 1
for left in range(-1, n - 1):
if left != -1:
lsum += nums[left]
while right < n and lsum + rsum > x:
rsum -= nums[right]
right += 1
if lsum + rsum == x:
ans = min(ans, (left + 1) + (n - right))
return -1 if ans > n else ans