1、找出数组中和为目标值的两个数

1、问题

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

2、思路

• 思路1： 两个循环，遍历两次解决我问题，时间复杂度O(n2)
• 思路2：先排序，再从两端（low,high）向中间靠近，两数和大于目标值high--，两数和小于目标值low++，时间复杂度o(logn)
• 思路3：两次循环：
  第一次：数组转HashMap<value,index>，
  第二次循环，循环值存入tmp：通过target与tmp在map中获取到值，且获取到的index与当前数据index值不等，两次循环，时间复杂度O（n）
• 思路4：是思路3的升级，一次循环搞定：
  初始空map，target与tmp差值在map中获取到值，则成功返回；
  否则将目tmp和index存入map中，时间复杂度O（n），较思路3时间更短

3、思路4的实例（java）

  public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int index1 = 0; index1 < nums.length; index1++) {
            Integer sTarget = target - nums[index1];
            Integer index2 = map.get(sTarget);
            if (index2 != null && index1 != index2) {
                int result[] = {index2, index1};
                return result;
            }
            map.put(nums[index1], index1);
        }
        return null;
    }