Java [leetcode 1] Two Sum

浏览数：33 / 时间：2015年06月08日

小二终于开通博客了，真是高兴。最近在看Java，所以就拿leetcode练练手了。以后我会将自己解体过程中的思路写下来，分享给大家，其中有我自己原创的部分，也有参考别人的代码加入自己理解的部分，希望大家看了多提意见，一块加油。

问题描述：

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

解体思路：

设立一个HashMap，其中键值key为数组中数值，对应值value则为该数组下标值。

从数组最开始往后遍历，每次求出该值对应target-numbers[i]的值在HashMap中是否存在。如果该值已经存在，那么则找到两个值的和为target值，返回即可；如果该值不存在，则把（numbers[i], i）放入HashMap中。

整个算法的时间复杂度为O(n)。

代码如下：

 1 public class Solution {
 2     public int[] twoSum(int[] numbers, int target) {        
 3         Map<Integer, Integer> map = new HashMap<Integer, Integer>(numbers.length * 2);
 4         int[] results = new int[2];
 5          
 6         for(int i = 0; i < numbers.length; i++){
 7             Integer temp1 = map.get(target - numbers[i]);
 8             if(temp1 == null){
 9                 map.put(numbers[i], i);
10             }
11             else{
12                 results[0] = i + 1;
13                 results[1] = temp1 + 1;
14                 if(results[0] > results[1]){
15                     int temp2 = results[0];
16                     results[0] = results[1];
17                     results[1] = temp2;
18                 }
19                 return results;
20             }
21         }   
22         return null;      
23     }
24 }