Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
给定一个整数数组，要求找到数组中的2个值，使他们的和等于给定值，并返回索引位置组成的数组（以1开始的索引）
我的解法：两层循环，从数组的第一个数开始和第j个数做比较，和目标值相同则返回，时间复杂度O(n2)
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[i]+nums[j] == target) { return new int[]{i+1,j+1}; } } } return null; }
优秀解法：一层循环，运用哈希表去重，数组值为key，索引为value。并使用哈希表的containsKey方法和目标值做比较，少去一次循环。
还有一个小细节，就是先去判断哈希表中有无符合条件的值，再去往里面插入，那么可以少去一次插入的步骤。
public int[] TwoSum2(int[] nums, int target) { Hashtable hsNums = new Hashtable(); for (int i = 0; i < nums.Length; i++) { if (hsNums.ContainsKey(target - nums[i])) { return new int[] { (int)hsNums[target - nums[i]],i + 1 }; } if (!hsNums.ContainsKey(nums[i])) hsNums.Add(nums[i], i + 1); } return null; }
原文：http://www.cnblogs.com/davidlidvd/p/5107423.html