Two Sum

Two Sum

 

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 

 

Naive Way:如果序列是排好序的，可不可以Binary Search。联想3sum的做法，好像可以。但是如果不是排好序的就不行，因为要返回Index而非boolean值，排序会打乱index。可不可以在O(n)的时间内做出来。可以，用一个HashTable去存已经遍历过的。

这是O(n) run time, O(n) space的做法。

 

 public class Solution {  
   public int[] twoSum(int[] numbers, int target) {  
     int rslt[] = {-1,-1};  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     for(int i = 0;i < numbers.length;i++){  
       int t = target - numbers[i];  
       if(map.containsKey(t)){  
         rslt[0] = map.get(t);  
         rslt[1] = i+1;  
         return rslt;  
       }else{  
         map.put(numbers[i],i+1);  
       }  
     }  
     return rslt;  
   }  
 }