Two Sum

Two Sum是各种面试题当中的经典题目。题目是给定一个目标和和一个数组，找出和等于目标和的所有数对。题目的解法有很多，比如使用hash map把数组进行hash存储，之后查找每个元素是否可以找到对应的值是否存在于hashmap当中。这样的解法的时间复杂度是O(n)，空间复杂度也是O(n)。另外一种方法是将一个数组排序，之后使用两个指针，一个向后搜索，一个向前搜索，如果当前和小于目标和，左指针向右移动；反之右指针向左移动。这样的话时间复杂度是O(n)依赖于排序的复杂度，空间复杂度最好可以做到O(1)。往往面试官希望能给出第二种解法。第二种解法的java实现如下。

public class sol {

	/**
	 * 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
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] A = {150,24,79,50,88,345,3};
		int [] B = new sol().twoSum(A,200);
		System.out.println(B[0]);
		System.out.println(B[1]);
	}
	
	public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
		if(numbers == null || numbers.length == 0)
			return new int[2];
		
		int [] nums = numbers.clone();
		Arrays.sort(numbers);
		
		int i = 0;
		int j = numbers.length-1;
		
		while(i &lt; j){
			if(numbers[i]+numbers[j] == target){				
				break;
			}
			else if(numbers[i]+numbers[j] &lt; target){
				i++;
			}
			else {
				j--;
			}
		}
		
		int [] results = {-1,-1};
		for(int k = 0;k &lt; nums.length;k++){
			if(numbers[i] == nums[k] &amp;&amp; results[0] == -1){
				results[0] = k+1;
			}
			else if(numbers[j] == nums[k]&amp;&amp; results[1] == -1){
				results[1] = k+1; 
			}
		}
		Arrays.sort(results);
		return results;        
    }
}