LeetCode热题1：Two Sum

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

最简单，也最容易的就是double for循环，但是时间复杂度太高了，是O(n^2)；

其实，思维变换一下，我们是要在数组中找一个num 和 target -num的值，那我们可以搞成两个数组，第一个是原始数据nums1，第二个是target-num的数据nums2，这样的话，就变成了怎么在nums2数组中找到和nums1中相同的数，比如nums1 = {1,3,5,7,9}，target=6；nums2={5,3,1,-1,-3}；可以明显看出来，1,3,5在nums2中也存在，去除掉3(自身)，就是1,5了。

那么怎么快速在nums2中找到是否存在和nums1中相同的值呢，使用Hash表。

代码实现一：

1. 先把nums数组中值和索引存到HashMap中
2. 循环nums数组，查找是否存在target-num的key，同时找到的key不能是自身
3. 输出数组当前索引i，和找到值key对应的vlaue(目标索引)

import java.util.HashMap;
import java.util.Map;

public class twoSum {

    public static void main(String[] args) {
        int nums[] = {1,2,3,4,5};
        int target = 6;
        twoSum1(nums,target);

    }

    public static void twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        for(int i=0;i< nums.length;i++){
            int temp = target-nums[i];
            if(map.containsKey(temp) && map.get(temp)!=i){
                System.out.println(i+"==="+ map.get(temp));
            }
        }
    }

代码实现二：

代码实现一其实会有数据重复的问题，比如会出现{1,5} 和 {5,1}，下面的实现二不仅避免了重复问题，还是只循环了nums一次，降低了时间复杂度，从O(2n)降到了O(n)

import java.util.HashMap;
import java.util.Map;

public class twoSum {

    public static void main(String[] args) {
        int nums[] = {1,2,3,4,5};
        int target = 6;
        twoSum2(nums,target);

    }

    public static void twoSum2(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = target-nums[i];
            if(map.containsKey(temp) && map.get(temp)!=i){
                System.out.println(i+"==="+ map.get(temp));
            }
            map.put(nums[i],i);
        }
    }
    
}