递归实现LeetCode存在重复元素问题出错：末尾重复返回false

错误原因 #

你的代码核心问题是递归调用时没有返回子函数的执行结果。当递归的子函数找到重复元素并返回true时，当前函数并没有将这个结果传递回去，而是继续执行到末尾的return false，导致最终返回错误结果。

看这段关键代码：

if (i < nums.Length) {
    ContainsDuplicate(nums, i); // 调用递归但丢弃了返回值
}

即使子调用返回true，当前函数依然会执行后续的return false，覆盖了正确结果。

修复后的代码 #

只需要在递归调用时返回其结果即可：

public static bool ContainsDuplicate(int[] nums, int i = 0) {
    
    for (int j = i + 1; j < nums.Length; j++) {
        Console.WriteLine("for loop j:" + j + " for i:" + i + " " + nums[j] + " == " + nums[i] );
        
        if (nums[j] == nums[i]) { 
            return true; 
        }   
    }

    i++;
    Console.WriteLine("i++ = " + i);

    if (i < nums.Length) {
        // 返回递归调用的结果，不再丢弃
        return ContainsDuplicate(nums, i); 
    }

    return false;
}

修复验证 #

修复后你的测试用例执行结果会变为：

• case1: True（正确）
• case2: False（正确）
• case3: True（正确，原错误返回False）
• case4: True（正确，原错误返回False）

补充优化建议 #

递归实现该问题的时间复杂度为O(n²)，且递归深度过大时可能触发栈溢出。实际解题更推荐用哈希集合（HashSet）实现，时间复杂度O(n)、空间复杂度O(n)，代码更简洁高效：

public static bool ContainsDuplicate(int[] nums) {
    HashSet<int> seen = new HashSet<int>();
    foreach (int num in nums) {
        if (!seen.Add(num)) {
            return true;
        }
    }
    return false;
}

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