LeetCode 1658: Minimum Operations to Reduce X to Zero (Transform to Longest Kept Subarray)
LeetCode 1658Sliding WindowArrayToday we solve LeetCode 1658 - Minimum Operations to Reduce X to Zero.
Source: https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/
English
Problem Summary
You are given an array nums and an integer x. In one operation, remove the leftmost or rightmost element from nums and subtract it from x. Return the minimum operations to reduce x to exactly 0, or -1 if impossible.
Key Insight
Removing from both ends is equivalent to keeping one middle subarray. If total sum is S, and removed sum must be x, then kept subarray sum must be S - x. So we need the longest subarray with sum target = S - x. Answer is n - longestLen.
Why This Works
Any sequence of end removals leaves a contiguous middle segment. Conversely, any middle segment corresponds to removing its left and right outside parts. Therefore minimizing removals equals maximizing kept segment length.
Optimal Algorithm (Sliding Window, positive nums)
1) Compute target = sum(nums) - x.
2) If target < 0, impossible → -1.
3) If target == 0, must remove all elements → n.
4) Use sliding window to find longest subarray with sum exactly target.
5) If not found, return -1; else return n - longestLen.
Complexity Analysis
Time: O(n).
Space: O(1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minOperations(int[] nums, int x) {
int total = 0;
for (int v : nums) total += v;
int target = total - x;
if (target < 0) return -1;
if (target == 0) return nums.length;
int left = 0, sum = 0, best = -1;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum == target) {
best = Math.max(best, right - left + 1);
}
}
return best == -1 ? -1 : nums.length - best;
}
}func minOperations(nums []int, x int) int {
total := 0
for _, v := range nums {
total += v
}
target := total - x
if target < 0 {
return -1
}
if target == 0 {
return len(nums)
}
left, sum, best := 0, 0, -1
for right, v := range nums {
sum += v
for sum > target && left <= right {
sum -= nums[left]
left++
}
if sum == target {
cur := right - left + 1
if cur > best {
best = cur
}
}
}
if best == -1 {
return -1
}
return len(nums) - best
}class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int total = accumulate(nums.begin(), nums.end(), 0);
int target = total - x;
if (target < 0) return -1;
if (target == 0) return (int)nums.size();
int left = 0, sum = 0, best = -1;
for (int right = 0; right < (int)nums.size(); ++right) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum == target) {
best = max(best, right - left + 1);
}
}
return best == -1 ? -1 : (int)nums.size() - best;
}
};class Solution:
def minOperations(self, nums: list[int], x: int) -> int:
total = sum(nums)
target = total - x
if target < 0:
return -1
if target == 0:
return len(nums)
left = 0
window_sum = 0
best = -1
for right, val in enumerate(nums):
window_sum += val
while window_sum > target and left <= right:
window_sum -= nums[left]
left += 1
if window_sum == target:
best = max(best, right - left + 1)
return -1 if best == -1 else len(nums) - bestvar minOperations = function(nums, x) {
const total = nums.reduce((a, b) => a + b, 0);
const target = total - x;
if (target < 0) return -1;
if (target === 0) return nums.length;
let left = 0;
let sum = 0;
let best = -1;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum === target) {
best = Math.max(best, right - left + 1);
}
}
return best === -1 ? -1 : nums.length - best;
};中文
题目概述
给定数组 nums 和整数 x。每次操作你可以删除数组最左或最右的元素，并把该值从 x 中减掉。要求最少操作次数使 x 恰好变成 0，做不到返回 -1。
核心思路
从两端删除，等价于保留中间一段连续子数组。设数组总和为 S，删除元素和必须是 x，那么保留子数组和就是 S - x。问题变成：找和为 target = S - x 的最长子数组。答案为 n - 最长长度。
为什么等价
任意两端删除序列，最后留下的部分一定是连续中段；反过来，任意中段都对应“删掉左边+删掉右边”。因此“最少删除”就是“最多保留”。
最优算法（正数数组下的滑动窗口）
1）计算 target = sum(nums) - x。
2）若 target < 0，无解返回 -1。
3）若 target == 0，说明必须删光，返回 n。
4）用滑动窗口寻找和恰好等于 target 的最长连续子数组。
5）若没找到返回 -1，否则返回 n - 最长长度。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minOperations(int[] nums, int x) {
int total = 0;
for (int v : nums) total += v;
int target = total - x;
if (target < 0) return -1;
if (target == 0) return nums.length;
int left = 0, sum = 0, best = -1;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum == target) {
best = Math.max(best, right - left + 1);
}
}
return best == -1 ? -1 : nums.length - best;
}
}func minOperations(nums []int, x int) int {
total := 0
for _, v := range nums {
total += v
}
target := total - x
if target < 0 {
return -1
}
if target == 0 {
return len(nums)
}
left, sum, best := 0, 0, -1
for right, v := range nums {
sum += v
for sum > target && left <= right {
sum -= nums[left]
left++
}
if sum == target {
cur := right - left + 1
if cur > best {
best = cur
}
}
}
if best == -1 {
return -1
}
return len(nums) - best
}class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int total = accumulate(nums.begin(), nums.end(), 0);
int target = total - x;
if (target < 0) return -1;
if (target == 0) return (int)nums.size();
int left = 0, sum = 0, best = -1;
for (int right = 0; right < (int)nums.size(); ++right) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum == target) {
best = max(best, right - left + 1);
}
}
return best == -1 ? -1 : (int)nums.size() - best;
}
};class Solution:
def minOperations(self, nums: list[int], x: int) -> int:
total = sum(nums)
target = total - x
if target < 0:
return -1
if target == 0:
return len(nums)
left = 0
window_sum = 0
best = -1
for right, val in enumerate(nums):
window_sum += val
while window_sum > target and left <= right:
window_sum -= nums[left]
left += 1
if window_sum == target:
best = max(best, right - left + 1)
return -1 if best == -1 else len(nums) - bestvar minOperations = function(nums, x) {
const total = nums.reduce((a, b) => a + b, 0);
const target = total - x;
if (target < 0) return -1;
if (target === 0) return nums.length;
let left = 0;
let sum = 0;
let best = -1;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > target && left <= right) {
sum -= nums[left++];
}
if (sum === target) {
best = Math.max(best, right - left + 1);
}
}
return best === -1 ? -1 : nums.length - best;
};
Comments