qingyan1990/blog

blog's Issues

leetcode题解——Two Sum

题目
我们要对给定的数组进行遍历，在遍历的过程中需要记录之前已经出现过的数字。采用什么数据结构来记录呢？数组的查询效率太低，Set的查询效率虽是O(1),但题目要求返回的是元素的索引，set只能记录一个值，也不符合。查询是O(1)，可以记录类似[值-索引]的记录的数据结构那么肯定是Map了。数据结构确定下来，代码就很简单了。

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