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):

The return format had been changed to zero-based indices. Please read the above updated description carefully.

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;
        while (head < tail) {
            if (nums2[head] + nums2[tail] == target) {
                min = head;
                max = tail;
                break;
            } else if (nums2[head] + nums2[tail] < target) {
                head++;
            } 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;
    }
}