1. 两数之和

难度：简单
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

有两种解法Java实现：

/**
 * 实现一
 * 复杂度分析
 * 时间复杂度O(n^2) 空间复杂度O(1)
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSum(int[] nums, int target) {
    int[] target_arr = new int[2];
    for(int i=0;i<nums.length;i++) {
        for(int j=i+1;j<nums.length;j++) {
            if(nums[i]+nums[j]==target) {
                target_arr[0] = i;
                target_arr[1] = j;
                return target_arr;
            }
        }
    }
    return target_arr;
}
/**
 * 实现二
 * 复杂度分析
 * 时间复杂度O(n) 空间复杂度O(n)
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSum2(int[] nums, int target) {
    int[] arr = new int[2];
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++) {
        int n = target-nums[i];
        if(map.containsKey(n)) {
            arr[0] = i;
            arr[1] = map.get(n);
            return arr;
        }
        map.put(nums[i], i);
    }
    return arr;
}