Dictionary.ContainsKey() 无法按预期工作

Question

我目前正在尝试解决第一道 Leetcode 问题（Two Sum）：

给定一个整数数组 nums 和一个整数目标，返回索引 两个数字的总和达到目标。

您可以假设每个输入都有一个解决方案，并且 您不能两次使用相同的元素。

您可以按任何顺序返回答案。

示例1：

输入：nums = [2,7,11,15]，目标 = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9，所以我们返回 [0, 1]。

示例2：

输入：nums = [3,2,4]，目标 = 6

输出：[1,2]

示例3：

输入：nums = [3,3]，目标 = 6

输出：[0,1]

这是我的代码：

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[]{};
    }

此代码工作正常，直到我多次获得包含相同元素的列表。

例如：

输入：nums = [2,7,11,15]，目标 = 9

返回：[1,0]

输入：nums = [1,1,1,1,1,4,1,1,1,1,1,7,1,1,1,1,1] 目标 = 11

返回：“未处理的异常。System.ArgumentException：已添加具有相同键的项目。键：1”

所以程序正在尝试在我的字典中添加另一个“1”键。我认为这是因为即使值相同，对象也不同，但我找不到如何解决这个问题。

有什么帮助吗？谢谢！

Answer 1

正如您所注意到的，您无法在字典中再次添加相同的键，但是您没有正确检查该键是否已存在：

int complement = target - nums[i];
if (hash.ContainsKey(complement))
{
    // ...
}
else
{
   hash.Add(nums[i], i); // boom, because target - nums[i] is unequal nums[i]
}

您可以使用以下方法，该方法使用一些 LINQ 并将索引存储为键：

public static int[] TwoSum(IList<int> nums, int target)
{
    if (nums.Count < 2)
    {
        return new int[] { };
    }

    Dictionary<int, int> indexAndValues = new() { { 0, nums[0] } };
    for (int i = 1; i < nums.Count; i++)
    {
        int num = nums[i];
        int matchingFirstIndex = indexAndValues
            .Where(x => x.Value + num == target)
            .Select(kv => kv.Key)
            .DefaultIfEmpty(-1)
            .First();
        if (matchingFirstIndex != -1)
        {
            return new int[] { matchingFirstIndex, i };
        }

        indexAndValues.Add(i, num);
    }

    return new int[] { };
}