leecode是一个训练编程的网站，今天开始用C#带大家一起闯关。

第一关叫 两数之和。

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示与进阶

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

难度与通过率

开始闯关

说实话我确实没想到第一关就稍有难度，而不是像其他游戏那种，前面几关都是送分题。

看上面统计的通过率就知道了，才52.8%。当然这其中可能也是因为很多人都是以第一关好奇，开始试试。

废话不多说，我们开始闯关。

首先得先读懂题，结合示例，一句话概括就是：找到数组中两数之和为给定值的那两个，并返回它们的下标。

常规思路就是把这个数组嵌套循环，外层循环从头到尾遍历，每次循环取当前位置作为第一个数，内层循环从外层循环的起始位置+1，每次循环取当前位置作为第二个数，两数相加等给定值，记录位置，程序结束，不想等就继续。

思路有了，代码如下：

int[] results = new int[2];
for (int i=0; i

提交验证，一次通过。可惜执行用时排名38.6%，效率稍微低点。

初级目标完成了，然后想能否做优化。

第一次优化

我刚开始以为两数之和等于target，那就说明其中的一个数小于等于target，那么也就是说只要外层循环中数组某个数大于target，内层就不需要继续做了。所以我改进了一下算法：

int[] results = new int[2];
for (int i=0; i target) continue;
    for (int j=i+1; j

增加了

if (nums[i] > target) continue;

的判断。结果提交报错了

原来数组中可以有负数，这个优化行不通。

第二次优化

if (nums[i] + nums[j] == target)

这个判断我之前放在了内层循环，所以假设数组长度是N，那这条语句的执行次数是N²级别的。我们知道这个nums[i] + nums[j] == target实际上两条语句，一是nums[i] + nums[j]的加法，二是相加结果与target的比较判断。如果我们利用数学公式，把表达式转换成这样：

if (target - nums[i] == nums[j])

效果是一样的。但这样，就为我们的优化奠定了基础。因为target - nums[i]与内层循环j变量无关，可以拿到外层循环中计算。于是我们可以再次做出优化：

int[] results = new int[2];
for (int i=0; i

这样就减少了一条N²语句的执行。提交后的效果，执行用时排名66.18%。

相比最初的算法，有所提升，但不到70分，也就基本上能称为良。还有更快的办法吗？

在这个题目的进阶中提示：你可以想出一个时间复杂度小于 O(n2) 的算法吗？那我们接下来就按照这个思路进行下去。

第三次优化

我不是计算机科班出身，对算法这块并不擅长。所以什么时间复杂度、空间复杂度这些我只是大概了解那么一点意思。这个时间复杂度小于 O(n2)，其实n2应该是n²，我的理解就是前面嵌套的那种双重循环。小于n²的意思，那就是不用双重循环。可以做到吗？

其实经过第二次优化，我们其实已经窥到了一丝门路。我们通过从求和转变成了求差，那其实完全可以做两次循环，第一次循环求差，然后把差和位置记录下来；第二次循环做比较，只要存在对应的差就算是找到了。这样只需要做两次循环（时间复杂度是2n），而不是两重循环（时间复杂度是n²）。

当然这里记录差和位置，数组肯定无法满足了，需要用到Hashtable。第三次优化后的代码：

int[] results = new int[2];
Hashtable ht = new Hashtable();

for (int i=0; i

看着没啥问题，但是遇到这个测试用例时无法满足：

需要继续优化代码，两次位置不能相同。

int[] results = new int[2];
Hashtable ht = new Hashtable();

for (int i=0; i

上面的案例得到满足，但是又遇到这个案例无法满足：

[3,3]
6

直接爆掉了。继续优化代码：

int[] results = new int[2];
Hashtable ht = new Hashtable();

for (int i=0; i

这次全部通过了。看看我们的最终战果：

排名96.72%，可以称为优等生了。当然执行效率的提升，是牺牲了内存空间换来的。

大家还有什么解题思路或更快的方法， 可以在评论区留言。