Two Sum

1. Two Sum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2,7,11,15], 

target =9,

Because nums[0] + nums[1] =2+7=9,

return[0,1].

给定一个整数数组，当两个数相加等于目标值时，返回其下表。

你可以假设每一组输入都仅有一个确切的结果，你不可以使用同样的元素两次。

Solution

Brute Force/暴力破解

遍历每一个元素x，并且寻找另一个元素y，使得y = target - x。

复杂度分析

时间复杂度：O(n​2)

对于每个元素，我们试图通过遍历数组中的其他元素O(n2)来找到匹配的结果。因此，时间复杂度是O(n​2)。

空间复杂度：O(1)

Tow-pass Hash Table/二次遍历散列表

为了改进时间复杂度，我们需要一种更有效的方式来检查数组中是否存在对应的元素。如果对应元素存在，我们需要查询它的下标。我们可以通过Hash表来存储每一个元素的下标。

我们使用hash表来将查询的时间复杂度从O(n)降到O(1)。hash表的查询时间近似于一个常量，但是当碰撞发生时，一次查询可能需要O(n)的时间。当hash方法选择得当时，一次查询的时间仅需要O(1)。

一个简单的实现就是使用二次遍历。在第一次遍历时，我们将每一个元素的值和下标添加到hash表中。然后，在第二次遍历时，我们查询每个元素的对应值是否存在(target - nums[i])。注意对应值不能是nums[i]自身。

复杂度分析

时间复杂度：O(n)。我们遍历了包含n个元素的列表两次。通过hash表将查询时间下降到O(1)，因此时间复杂度是O(n)。

空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间，因此空间复杂度是O(n)。

One-pass Hash Table/一次遍历散列表

我们可以使用一次遍历来实现。当我们遍历并且插入元素的时候，我们同时回看并且复查是否有对应的元素已经存在于散列表中。如果存在我们就得到了一个解，并且立刻返回结果。

复杂度分析

时间复杂度：O(n)。我们遍历了包含n个元素的列表一次。每次查询耗时O(1)。

空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间。