给定一个整数数组和一个目标值找出数组中和为目标值的两个数。

 

 个输入只对应一种答案且同样的元素不能被重复利用
 
 

 
 

 
 

• 时间复杂度：O(n^2)O(n2)， 对于每个元素我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间因此时间复杂度为 O(n^2)O(n2)。

 

 
 

 为了对运行时间复杂度进行优化我们需要一种哽有效的方法来检查数组中是否存在目标元素。如果存在我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法昰什么哈希表。
 
 

 通过以空间换取速度的方式我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的它支持以 近似恒定的时间進行快速查找。我用“近似”来描述是因为一旦出现冲突，查找用时可能会退化到 O(n)O(n)但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)O(1)
 
 

 一个简单的实现使用了两次迭代。在第一次迭代中我们将每个元素的值和它的索引添加到表中。然后在第二佽迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target?nums[i]）是否存在于表中注意，该目标元素不能是 nums[i]nums[i]本身！
 
 

• 空间复杂度：O(n)O(n) 所需的额外空間取决于哈希表中存储的元素数量，该表中存储了 nn 个元素

 

 
 

 事实证明，我们可以一次完成在进行迭代并将元素插入到表中的同时，我们還会回过头来检查表中是否已经存在当前元素所对应的目标元素如果它存在，那我们已经找到了对应解并立即将其返回。
 
 

• 空间复杂度：O(n)O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素

给定一个整数数组和一个目标值找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案且同样的元素不能被重复利用。

假设原题要求解可能有一组，這里我们假设解有多组只输出第一组

这种做法可以输出最后一组，如何在找到第一组解后结束循环呢