LeetCode将x减到0的最小操作数递归代码运行异常求助

问题代码 #

def min_num(nums,x):
    
    f_ele = nums[0]
    l_ele = nums[-1]
    count = 0

    if min(x - f_ele, x - l_ele ) >= 0:
        count += 1
        #modifying x and nums
        if x - f_ele == min(x - f_ele, x - l_ele ):
            x = x - f_ele
            nums.remove(f_ele)  
        else:
            x = x - l_ele
            nums.remove(l_ele) 
        
        #Comparing x to use recursion or return the count
        if x != 0: 
            min_num(nums,x)
        else:
            return count

    elif x == 0:
        return count
    
    else:
        return -1

核心错误点 #

你的代码存在4个致命问题，直接导致逻辑失效、运行异常：

• 递归返回值丢失：在x != 0的分支中，你仅调用了min_num(nums,x)，没有接收递归调用的返回值，也没有将当前层的计数和递归层的结果做累加，下层递归算出的结果直接被丢弃，根本无法返回正确的总操作数。
• 计数变量作用域错误：count是定义在函数内部的局部变量，每次进入新的递归层都会被重置为0，哪怕正确接收了返回值，也无法正确统计全局的操作次数。
• 贪心逻辑不成立：你每次仅选择两端元素中让剩余x更小的那一个，这种局部最优的选择无法得到全局最优解。存在大量场景：某一步选更小的剩余值后续会走到死路，但选稍大的剩余值反而能凑出最终解，你的代码会直接选错路径。
• 边界和回溯缺失：当某一端选择走不通时，你没有回退状态尝试另一端的选项；当数组被删空时还在访问nums[0]和nums[-1]，会直接触发索引越界错误。

这道题不适合用朴素递归/回溯实现，当数组长度达到10^5量级时回溯会直接超时，推荐用滑动窗口思路：

1. 先计算数组全体元素的总和total
2. 原问题等价转化为：找到数组中最长的连续子数组，满足它的元素和等于total - x
3. 最终的最小操作数 = 数组总长度 - 这个最长子数组的长度，如果不存在符合要求的子数组则返回-1

这个解法时间复杂度为O(n)，空间复杂度O(1)，可以稳定通过所有测试用例。

内容的提问来源于stack exchange，提问作者Arnav Rajurkar