Two Sum

**Two Sum **

题目描述：
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
翻译后的大致意思是：
从给定的数组中找两个元素，使得 两个元素的值满足 所给的要求 target，注意：输出的不是下标，而是元素的位置(或者说是第几个元素)

具体的方法有三种：

1. 暴力法，复杂度为O(n2)，会超时
2. 使用一个哈希表，存储元素及其下标，复杂度为O(n)
3. 先排序，然后左右夹逼，排序O(nlogn)，左右夹逼O(n)，最终O(nlogn)，但是这是返回数子本身并不是返回下标，这题要返回的是下标

public class Solution04 {
    public int[] twoSum(int[] nums, int target) {
        // 定义一个hash表来存储每个数和对应的下标
        final HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 注意 (K,V) 的位置
            // 起初我就是把key和value定义反了导致查找 target - value 时不能找到 index
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            // 获取 target - num[i] 也就是 target - value 的值的对应的index
            final Integer v = map.get(target - nums[i]);
            // 判断对应的 index 是否存在且大于当前的下标
            if (v != null && v > i) {
                return new int[]{i + 1, v + 1};
            }
        }
        // 不存在返回 null
        return null;
    }
}

class Main04 {
    public static void main(String[] args) {
        Solution04 solution04 = new Solution04();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] ints = solution04.twoSum(nums, target);
        System.out.println(Arrays.toString(ints));
    }
}