文章目录题目描述解法一暴力解解法二逆向思维 滑动窗口 (最优解)边界条件与错误处理1. targetSum 0x 大于总和2. targetSum 0需要移除所有元素3. 数组为空4. 无法凑成 xmaxLen 保持 -15. 边界情况汇总测试题目描述提示1 nums.length 1051 nums[i] 1041 x 109解法一暴力解解题思路最直观的想法是直接模拟操作。我们可以尝试移除左边的 i 个元素然后看看需要从右边移除多少个元素 j 才能使和为 x。具体步骤预计算数组的前缀和 prefixSum 和后缀和 suffixSum这样可以 O(1) 查询。外层循环 i 从 0 到 n (包括不移除任何左边元素的情况)。对于每一个 i计算左边移除 i 个元素的和 leftSum prefixSum[i]。我们需要从右边移除元素的和为 rightSum x - leftSum。在后缀和中查找是否存在一个 j使得移除 j 个元素的和等于 rightSum。为了快速查找可以预先将后缀和及其对应的长度存入一个哈希映射中。如果找到了总操作数就是 i j。我们用一个变量来记录和更新最小的操作数。需要注意 ij 不能超过数组总长度 n。代码实现defminOperations(nums,x):nlen(nums)# 预计算前缀和prefixSum[0]*(n1)foriinrange(n):prefixSum[i1]prefixSum[i]nums[i]# 预计算后缀和suffixSum[0]*(n1)foriinrange(n-1,-1,-1):suffixSum[i]suffixSum[i1]nums[i]# 将后缀和及其对应的移除个数存入哈希映射suffixMap{}forjinrange(n1):suffixMap[suffixSum[j]]j ansfloat(inf)# 枚举左边移除 i 个元素foriinrange(n1):leftSumprefixSum[i]rightSumx-leftSumifrightSuminsuffixMap:jsuffixMap[rightSum]ifijn:ansmin(ans,ij)return-1ifansfloat(inf)elseans# 示例测试if__name____main__:# 示例 1nums1[1,1,4,2,3]x15print(minOperations(nums1,x1))# 输出: 2# 示例 2nums2[5,6,7,8,9]x24print(minOperations(nums2,x2))# 输出: -1# 示例 3nums3[3,2,20,1,1,3]x310print(minOperations(nums3,x3))# 输出: 5执行结果2 -1 5复杂度分析时间O(n)空间O(n)解法二逆向思维 滑动窗口 (最优解)解题思路关键的思路转换 让我们换一个角度看问题 题目要求我们找到一个最短的、由数组前缀和后缀组成的序列其和为 x。如果我们从数组中移除了一个前缀和一个后缀剩下的是什么是一个连续的、位于中间的子数组。 假设数组的总和是totalSum。如果我们移除了和为 x 的元素那么剩下的中间子数组的和必然是 totalSum - x。原问题“找到和为 x 的最短前后缀”新问题“找到和为 totalSum - x 的最长连续子数组”具体步骤计算目标和首先计算整个数组的总和 totalSum。计算我们中间子数组的目标和 targetSum totalSum - x。处理边界情况如果 targetSum 0说明 x 比总和还大永远不可能凑成直接返回 -1。如果 targetSum 0这意味着我们需要移除所有元素才能使和为 x。此时最长的中间子数组长度为 0所以答案是 n (总操作数)。应用滑动窗口初始化左指针 start 0当前窗口和 currentSum 0。初始化 maxLen -1 (用于记录找到的最长子数组长度-1 表示还没找到)。使用右指针 end 从 0 遍历到 n-1a. 扩大窗口currentSum nums[end]。b. 收缩窗口当 currentSum targetSum 时我们需要从左边移出元素来缩小 sum。进入一个 while 循环currentSum - nums[start]然后 start直到 currentSum targetSum。c. 检查匹配在收缩窗口后如果 currentSum targetSum说明我们找到了一个满足条件的中间子数组。我们用它的长度 end - start 1 来更新 maxLen。 maxLen max(maxLen, end - start 1)。计算最终结果滑动窗口结束后如果 maxLen 仍然是 -1说明从未找到和为 targetSum 的子数组即无法凑成 x返回 -1。如果找到了 maxLen那么最小操作数就是数组总长度 n 减去这个最长的保留子数组的长度。最终答案是 n - maxLen。代码实现代码实现defminOperations(nums,x):nlen(nums)totalSumsum(nums)targetSumtotalSum-x# 边界情况x 比总和还大无法凑成iftargetSum0:return-1# 边界情况需要移除所有元素iftargetSum0:returnn start0currentSum0maxLen-1# 滑动窗口forendinrange(n):currentSumnums[end]# 收缩窗口whilecurrentSumtargetSumandstartend:currentSum-nums[start]start1# 检查是否匹配ifcurrentSumtargetSum:maxLenmax(maxLen,end-start1)return-1ifmaxLen-1elsen-maxLen# 示例测试if__name____main__:# 示例 1nums1[1,1,4,2,3]x15print(minOperations(nums1,x1))# 输出: 2# 示例 2nums2[5,6,7,8,9]x24print(minOperations(nums2,x2))# 输出: -1# 示例 3nums3[3,2,20,1,1,3]x310print(minOperations(nums3,x3))# 输出: 5执行结果2 -1 5复杂度分析时间O(n)空间O(1)边界条件与错误处理滑动窗口解法虽然简洁但正确性高度依赖几个边界条件的处理。下面逐一说明并给出对应的测试用例。1. targetSum 0x 大于总和当x比整个数组的总和totalSum还大时targetSum totalSum - x 0此时无论怎么移除都不可能凑出和为x的前后缀直接返回-1。# 测试用例x 大于总和nums[1,2,3]x10print(minOperations(nums,x))# 输出: -12. targetSum 0需要移除所有元素当x恰好等于totalSum时targetSum 0意味着中间保留的子数组长度为 0即需要把整个数组全部移除操作数为n。# 测试用例x 等于总和需要移除全部元素nums[1,2,3]x6print(minOperations(nums,x))# 输出: 33. 数组为空虽然题目约束1 nums.length但作为健壮性考虑若传入空数组当x 0时无需任何操作返回0当x 0时无法凑成返回-1。# 测试用例空数组print(minOperations([],0))# 输出: 0print(minOperations([],5))# 输出: -14. 无法凑成 xmaxLen 保持 -1当targetSum 0但数组中不存在和为targetSum的连续子数组时maxLen始终为-1最终返回-1。# 测试用例无法凑成 xnums[5,6,7,8,9]x4print(minOperations(nums,x))# 输出: -15. 边界情况汇总测试将上述用例整合成一段可运行的完整测试脚本defminOperations(nums,x):nlen(nums)totalSumsum(nums)targetSumtotalSum-xiftargetSum0:return-1iftargetSum0:returnn start0currentSum0maxLen-1forendinrange(n):currentSumnums[end]whilecurrentSumtargetSumandstartend:currentSum-nums[start]start1ifcurrentSumtargetSum:maxLenmax(maxLen,end-start1)return-1ifmaxLen-1elsen-maxLen# 边界测试print(minOperations([1,2,3],10))# 输出: -1x 大于总和print(minOperations([1,2,3],6))# 输出: 3移除全部元素print(minOperations([],0))# 输出: 0空数组x0print(minOperations([],5))# 输出: -1空数组x0print(minOperations([5,6,7,8,9],4))# 输出: -1无法凑成print(minOperations([1,1,4,2,3],5))# 输出: 2常规用例以上所有边界情况都在代码中通过前置判断或滑动窗口的maxLen哨兵值得到了正确处理保证了算法在各种输入下的健壮性。