优化两数之和算法：降低时间复杂度及替换List实现为数组

嘿，很高兴你已经搞定了基础版的两数之和解法，还主动琢磨着优化的方向，这思路太赞了！咱们一步步来解决你提出的两个问题：把时间复杂度降下来，以及不用List改用数组存储结果。

一、把时间复杂度从O(n²)降到O(n)：用哈希表优化 #

你原来的双重循环思路虽然直观，但每次都要遍历后续元素，数据量大的时候效率会比较低。咱们可以用空间换时间的思路，借助哈希表（C#里的Dictionary<int, int>）来记录已经遍历过的元素和它的索引，这样一次循环就能找到答案：

1. 遍历数组时，对当前元素nums[i]，计算它和目标值的差值complement = target - nums[i]
2. 检查哈希表里有没有这个差值：
   • 如果有，说明之前已经遍历过这个差值对应的元素，直接返回之前元素的索引和当前索引i
   • 如果没有，就把当前元素和它的索引存入哈希表，继续遍历

对应的C#代码示例：

public int[] GetTarget(int[] nums, int target)
{
    // 键：数组元素值，值：元素对应的索引
    Dictionary<int, int> numDict = new Dictionary<int, int>();
    
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        if (numDict.ContainsKey(complement))
        {
            // 直接返回找到的两个索引，不用存List再转数组
            return new int[] { numDict[complement], i };
        }
        // 注意：如果有重复元素，这里会覆盖之前的索引，但题目一般假设只有唯一解，所以没问题
        if (!numDict.ContainsKey(nums[i]))
        {
            numDict.Add(nums[i], i);
        }
    }
    // 如果没找到符合条件的元素，返回null或者空数组，根据需求调整
    return null;
}

针对你的测试场景：arr = [2,4,6,10]，target=10，遍历到6（索引2）时，差值是10-6=4，哈希表里已经存了4对应的索引1，所以直接返回[1,2]，完美符合预期。

二、不用List，直接用数组存储结果 #

其实两数之和的结果最多就是两个索引，完全不需要用动态的List来存储！咱们可以直接初始化一个长度为2的数组，找到符合条件的元素时直接给数组赋值，然后返回就行。

哪怕是你原来的双重循环写法，也可以改成这样：

public int[] GetTarget(int[] nums, int target)
{
    int[] result = null;
    for (int i = 0; i < nums.Length - 1; i++)
    {
        for (int j = i + 1; j < nums.Length; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                // 直接创建长度为2的数组赋值
                result = new int[] { i, j };
                // 找到结果后可以直接跳出循环，不用继续遍历
                break;
            }
        }
        // 找到结果就退出外层循环
        if (result != null)
        {
            break;
        }
    }
    return result;
}

这样就彻底摆脱了List，直接用固定长度的数组存储结果，逻辑更简洁，也避免了List转数组的额外操作。

总结一下：用哈希表的方法把时间复杂度降到O(n)，同时因为结果固定是两个索引，直接用长度为2的数组存储就足够啦！

备注：内容来源于stack exchange，提问作者user8512043