使用递归思路求解两数之和的代码错误排查

错误点整理 #

• 辅助函数help_循环逻辑错误：循环内只要第一次判断不相等就直接返回False，不会遍历后续元素，除了首元素和第二个元素匹配的场景，其他情况都会误判为无结果。
• 递归调用逻辑错误：未找到匹配时你调用的是help_而非递归调用外层的twoSum方法，无法完成子列表的遍历校验。
• 偏移量ctn用法错误：ctn定义在twoSum内部，每次递归都会被重置为0，无法累计前面截断的元素个数，无法映射回原数组下标；且你写的ctn =+1是语法错误，正确的累加写法是ctn +=1。
• 递归返回值处理错误：递归调用子列表得到的下标是子列表内的相对下标，没有加上偏移量就直接返回，和原数组下标不匹配。

修正方案 #

完全按照你要求的「校验首元素和其余元素，不匹配则递归处理子列表」的思路修改，修正后代码如下：

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 辅助函数：校验当前列表首元素和其余元素之和是否等于target
        # 匹配返回对应元素的下标，不匹配返回False
        def help_(lst,tar):
            for i, n in enumerate(lst[1:],start=1):
                if lst[0]+n == tar:
                    return i
            # 遍历完所有元素都不匹配才返回False
            return False
                
        # 先校验当前列表首元素是否存在匹配项
        res_idx = help_(nums, target)
        if res_idx is not False:
            return [0, res_idx]
        else:
            # 递归处理去掉首元素的子列表，得到的结果每个下标加1（对应原数组的偏移）
            sub_res = self.twoSum(nums[1:], target)
            return [x + 1 for x in sub_res]

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