华为 OD 训练营 · 题解精讲
LC1658. 将x减到0的最小操作数
LC1658. 将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 <= 10^(5) 1 <= nums[i] <= 10^(4) 1 <= x <= 10^(9)
题目解析
解题思路
本题要求从数组两端移除元素，使移除元素之和等于 x，且操作次数最少。等价于在数组中寻找一个最长的连续子数组，其和为 sum(nums) - x，因为剩余部分就是需要移除的元素。这样，最小操作数 = 数组长度 - 最长子数组长度。
采用不定长滑动窗口（双指针）实现：维护窗口内元素和 windows_sum，当和大于目标值时收缩左边界，当和等于目标值时更新最大窗口长度。
关键步骤
1. 计算 target_sum = sum(nums) - x。若 target_sum == 0，直接返回 len(nums)（全部移除）。 2. 初始化左指针 left = 0，窗口和 windows_sum = 0，最大窗口长度 windows_len_max = 0。 3. 右指针 right 遍历数组：
- A1：将
nums[right]加入窗口和。 - A2：当窗口和大于目标值时，不断右移左指针并减去对应元素。
- A3：若窗口和等于目标值，更新最大窗口长度。
4. 遍历结束后，若最大窗口长度为 0，返回 -1；否则返回 len(nums) - windows_len_max。
示意图（以示例1 nums=[1,1,4,2,3], x=5 为例，target_sum=6）：
初始：窗口 [1,1,4] 和=6 → 长度3
最终：窗口 [1,1,4] 长度3 → 操作数=5-3=2复杂度分析
- 时间复杂度：O(n)，每个元素最多被左右指针各访问一次。
- 空间复杂度：O(1)，仅使用常数个变量。
参考代码
# 题目：LC1658. 将x减到0的最小操作数
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：不定滑窗
# 代码看不懂的地方，请直接在群上提问
# 本质上是求【和为target_sum = sum(nums) - x的滑动窗口的最大长度】
# 用变量 windows_sum 表示滑窗中所有元素的和即可
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
target_sum = sum(nums)-x
if target_sum == 0:
return len(nums)
windows_sum = 0
windows_len_max = 0
left = 0
for right, num in enumerate(nums):
# A1
windows_sum += num
# A2
while(left <= right and windows_sum > target_sum):
windows_sum -= nums[left]
left += 1
# A3
if windows_sum == target_sum:
windows_len_max = max(right-left+1, windows_len_max)
return -1 if windows_len_max == 0 else len(nums)-windows_len_max