两数之和(hash算法)
两数之和
http://www.nowcoder.com/questionTerminal/20ef0972485e41019e39543e8e895b7f
public int[] twoSum (int[] numbers, int target) { // write code here for(int i=0;i<numbers.length;i++) for(int j=i+1;j<numbers.length;j++) if(numbers[i]+numbers[j]==target) return new int[]{i+1,j+1}; return null; } }
采用哈希表,以空间换时间,避免重复,需要加一次判断
public int[] twoSum (int[] numbers, int target) { // write code here HashMap<Integer,Integer> m=new HashMap<Integer,Integer>(); for(int i=0;i<numbers.length;i++){ m.put(numbers[i],i+1); } //再次扫描队列 for(int i=0;i<numbers.length;i++){ if(m.containsKey(target-numbers[i])&&m.get(target-numbers[i])!=i+1) return new int[]{i+1,m.get(target-numbers[i])}; } return null; }