C#中Dictionary.ContainsKey()异常，LeetCode两数之和重复元素报错

问题描述 #

LeetCode第一题《两数之和》要求：给定整数数组nums和整数target，返回两个数的下标，使它们的和为target。题目假设输入必有唯一解，且不能重复使用同一元素。

原C#代码在数组无重复元素时正常运行，但遇到包含重复元素的数组时会抛出异常，例如输入nums = [1,1,1,1,1,4,1,1,1,1,1,7,1,1,1,1,1]、target=11时，报错：

Unhandled exception. System.ArgumentException: An item with the same key has already been added. Key: 1

原C#代码：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> hash = new Dictionary<int, int>();
        int n = nums.Count();

        for (int i=0; i < n; i++) {
            int complement = target - nums[i];
            if (hash.ContainsKey(complement)) {
                int[] solution = new int[]{(int)i, (int)hash[complement]};
                return solution;
            }
            else {
                hash.Add(nums[i], i);
            }
        }

        return new int[]{};
    }
}

相同逻辑的Python代码可正常运行，因为Python字典赋值时会直接覆盖重复键：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hash:
                return [i, hash[complement]]
            else:
                hash[nums[i]] = i

        return []

解决方法 #

问题出在C#的Dictionary.Add()方法：当键已存在时，该方法会抛出ArgumentException，而Python字典的赋值操作会直接覆盖旧值。我们只需要将C#中的hash.Add(nums[i], i)替换为字典索引器赋值hash[nums[i]] = i，索引器会自动处理键的存在性——不存在则添加，存在则覆盖旧值。

同时，数组的长度建议直接用nums.Length代替LINQ的nums.Count()，效率更高。

修改后的C#代码：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> hash = new Dictionary<int, int>();
        int n = nums.Length;

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (hash.ContainsKey(complement)) {
                return new int[]{i, hash[complement]};
            }
            // 索引器赋值：存在则覆盖，不存在则添加
            hash[nums[i]] = i;
        }

        return new int[]{};
    }
}

原理说明 #

题目保证输入有唯一解，所以：

• 如果当前元素的补码是之前出现过的重复元素，那么在遍历到那个重复元素时，它的补码（当前元素）还未被加入字典，不会触发返回；当遍历到当前元素时，补码已在字典中，此时返回的下标是正确的。
• 如果重复元素不是解的一部分，覆盖它们的下标不会影响结果，因为唯一解不会依赖这些重复元素的旧下标。

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