码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


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 < j){
			if(numbers[i]+numbers[j] == target){				
				break;
			}
			else if(numbers[i]+numbers[j] < target){
				i++;
			}
			else {
				j--;
			}
		}
		
		int [] results = {-1,-1};
		for(int k = 0;k < nums.length;k++){
			if(numbers[i] == nums[k] && results[0] == -1){
				results[0] = k+1;
			}
			else if(numbers[j] == nums[k]&& results[1] == -1){
				results[1] = k+1; 
			}
		}
		Arrays.sort(results);
		return results;        
    }
}
最近的文章

Best Time to Buy and Sell Stock

股票买卖是面试当中另外一个常见的问题。问题的描述是:给出一个数组,数组中的的数表示每个时刻股票的价格。如果只允许买卖一次,请写出一个算法给出可能的最大收益。基础的算法是对于一个个时刻,搜索其能得到的最…

Technical, Career继续阅读
更早的文章

工作基本敲定,我的找工作总结【楠哥原创】

原帖发于:http://www.1point3acres.com/bbs/thread-45678-1-1.html  拿到微软的Offer后,找工作这事儿终于可以暂告一个段落。在地里得到…

Career, Technical继续阅读
comments powered by Disqus