如何用递归解决两数之和问题？代码报错求修正

你的代码存在三个核心问题：

• 仅检查相邻元素：比如测试用例[3,2,3]中符合条件的是下标0和2，并非相邻元素，导致代码无法找到解
• 数组越界风险：当i为数组最后一个元素时，nums[i+1]会访问超出数组范围的内存，可能引发崩溃或错误结果
• 递归逻辑片面：仅递归检查下一对相邻元素，完全忽略了当前元素与后续所有非相邻元素的组合

修正后的代码 #

class Solution {
private:
    void giveSolution(vector<int>& nums, int i, int target, vector<int>& v, bool& found) {
        // 找到解或遍历到倒数第二个元素时终止递归
        if (found || i >= nums.size() - 1) {
            return;
        }
        // 遍历当前元素之后的所有元素，寻找匹配对
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[i] + nums[j] == target) {
                v.push_back(i);
                v.push_back(j);
                found = true;
                return;
            }
        }
        // 当前元素无匹配，递归处理下一个元素
        giveSolution(nums, i + 1, target, v, found);
    }

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        bool found = false;
        giveSolution(nums, 0, target, result, found);
        return result;
    }
};

关键改进点 #

• 新增found标记：一旦找到符合条件的下标对，立即标记并终止后续递归，避免无效计算
• 遍历后续所有元素：不再局限于相邻元素，覆盖所有可能的元素组合
• 完善终止条件：当i到达倒数第二个元素时停止递归，因为此时没有后续元素可以配对

测试验证 #

对于nums = [3,2,3], target = 6，当i=0时，j遍历到2，nums[0]+nums[2]=6，会正确记录下标0和2并返回结果。

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