LeetCode两数之和解法中字典数据来源及TryGetValue逻辑疑问

问题描述 #

我并非询问Dictionary<int, int> resultDictionary = new();这行代码，我清楚它的作用是初始化一个空Dictionary。我疑惑的是，resultDictionary.TryGetValue(secondNumber, out int index)这行代码中，TryGetValue方法所检查的数据来自哪里？以下代码声明了Dictionary，但我奇怪似乎没有填充数据的操作，能否有人解释其中的逻辑？

public class Solution {
    public int[] TwoSum(int[] nums, int target) 
    {
        //Declarations
            int arrayLength = nums.Length;
            Dictionary<int, int> resultDictionary = new();
            
            //Validations
            if (nums == null || arrayLength < 2)
            {
                return Array.Empty<int>();
            }

            //Logic
            for (int i = 0; i < arrayLength; i++)
            {
                int firstNumber = nums[i];
                int secondNumber = target - firstNumber;
                
                if (resultDictionary.TryGetValue(secondNumber, out int index))
                {
                    return new[] { index, i };
                }

                //resultDictionary.Add(firstNumber, i);
                resultDictionary[firstNumber] = i;
                //Console.Write(resultDictionary[firstNumber]);
            }

            return Array.Empty<int>(); 
        
    }
}

逻辑解释 #

其实这个Dictionary是在循环过程中逐步填充数据的，只是填充操作在TryGetValue判断之后，容易被忽略：

• 循环从数组的第0个元素开始遍历，每次先计算当前元素对应的补数：secondNumber = target - firstNumber
• 调用TryGetValue检查这个补数是否存在于Dictionary中——这里检查的是之前循环迭代里已经存入Dictionary的元素和索引
• 如果没找到匹配的补数，就把当前元素值firstNumber和它的索引i存入Dictionary（就是代码里的resultDictionary[firstNumber] = i;，这就是填充数据的核心操作）
• 后续循环迭代时，新元素的补数会去匹配之前所有已存入的数据，一旦找到，就直接返回对应的两个索引

举个实际例子辅助理解：假设输入数组是[2,7,11,15]，目标值为9

1. 第一次循环（i=0）：当前元素是2，补数是7。此时Dictionary为空，TryGetValue找不到7，于是把2:0存入Dictionary
2. 第二次循环（i=1）：当前元素是7，补数是2。此时Dictionary里已经有2:0，TryGetValue成功找到，直接返回[0,1]

这种写法是TwoSum算法的优化实现，通过空间换时间，把时间复杂度从暴力解法的O(n²)降到了O(n)，利用Dictionary的快速查找特性避免重复遍历数组。

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