# Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
``````

UPDATE (2016/2/13):

Tips:

HashMap 和 Two Pointers.O(n) Two Pointers要注意，先要clone，然后排序，找到两个数之后还要在原数组里找index。O(nlogn)

Code:

HashMap:

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

Two Pointers:

``````public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length ==0) {
return null;
}
int[] result = new int[2];
int[] nums2 = nums.clone();
Arrays.sort(nums2);
int head = 0, tail = nums2.length - 1;
int min = -1;
int max = -1;
if (nums2[head] + nums2[tail] == target) {
max = tail;
break;
} else if (nums2[head] + nums2[tail] < target) {
} else {
tail--;
}
}
int i = 0, j = 0;
for (i = 0; i < nums.length; i++){
if (nums[i] == nums2[min]){
result[0] = i;
break;
}
}
for (j = 0; j < nums.length; j++){
if (nums[j] == nums2[max] && j != i){
result[1] = j;
break;
}
}
Arrays.sort(result);
return result;
}
}
``````