Two Sum

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.
给一个整数数组，返回两个数相加是特定的目标和的下标。假设每次输入只有一个解。

Example:
　　给定数组nums = [2, 7, 11, 15], 目标和target = 9,因为 nums[0] + nums[1] = 2 + 7 = 9,返回[0,1].

UPDATE (2016/2/13):
The return format had been changed to **zero-based **indices. Please read the above updated description carefully.
返回格式改为基于0的小标，请仔细阅读以上的更新描述。

解1：

最简单的方式是嵌套遍历每个元素，与target比较，相等即返回，直至结束。代码如下(java)：
public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); }
　　显然时间复杂度为O(n^2),空间复杂度为O(1)。

解2：

解１的时间复杂度太高，显然不是最优解，我们通过提高空间复杂度，来减少时间复杂度。使用两个循环，第一个循环吧元素添加到map树，第二个循环在map中寻找target - nums[i]，要查询map中的元素，因此用hashmap存储数组。这样时间复杂度为O(n),因为要把数组存为map空间复杂度为O(1)。代码如下(java)：
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); }

解3：

仔细分析解２，我们可以将两个循环合并，通过查询已经插入的元素，直至最后，当map添加完元素，查询也结束了。而时间和空间复杂度，与解2相同。
代码(java):
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); }