Two Sum

Total Accepted: 37848 Total Submissions: 206006

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

第一次做leetcode看到这题第一感觉还是水题，简单的用C++的Vector做了一番，简单的用两个循环判断，结果直接超时了， 看来leetcode还是比较严格的不接受O(N^2)的数据。代码如下：

//由于忘记保存起先提交的代码，以下代码为自己的测试代码

class Solution {
public:
	void twoSum(vector<int> &numbers, int target) {
		vector<int> a = numbers;
		int index1, index2;
		for (int i = 0; i<a.size(); i++)
		{
			for (int j = i + 1; j<a.size(); j++)
			{
				if (a[i] + a[j] == target)
				{ 
					index1 = a[i];
					index2 = a[j];
					break;
				}
			}
		}
		if (index1>index2){
			int temp = index1;
			index1 = index2;
			index2 = temp;
		}
		cout << index1 << " " << index2 << endl;
	}
};

后来网上看别人的做法，才知道用Java的Hashtable来解题。

思路：循环一次，每次都判断当前数组索引位置的值在不在hashtable里，不在的话，加入进去，key为数值，value为它的索引值；在的话，取得他的key，记为n（此时n一定小于循环变量i），接下来再在hashtable中查找（target-当前数值）这个数，利用了hashtable中查找元素时间为常数的优势，如果找到了就结束，此处需要注意的是，如果数组中有重复的值出现，那么第二次出现时就不会加入到hashtable里了，比如3,4,3,6；target=6时，当循环到第二个3时，也可以得到正确结果。

最终AC代码：

import java.util.Hashtable;
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int []a=new int[2];
        Hashtable<Integer,Integer> num = new Hashtable<Integer,Integer>();
        for(int i=0;i<numbers.length;i++)
        {
            Integer n = num.get(numbers[i]);
            if(n==null) num.put(numbers[i],i);
            n = num.get(target-numbers[i]);
            if(n!=null&&n<i)
            {
                a[0]=n+1;
                a[1]=i+1;
            }
        }
        return a;
        }
}

这道题目，主要是要会使用Hashtable,通过这道题目还是能学习到蛮多的！

LeetCode Two Sum