LeetCode1-两数之和

题目描述

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

我的题解

暴力法

    public int[] twoSum(int[] nums, int target) {
        int [] res= new int[2];
        for (int i=0;i<nums.length-1;i++){
            for (int j=i+1;j<nums.length;j++){
                if (nums[i]+nums[j]==target){
                    res[0]=i;
                    res[1]=j;
                    break;
                }
            }
        }
        return res;
    }

字典法(Map)

拿到一个数a，我如果说能迅速判断是否存在b使a+b=target就好了
我们可以使用Map构造一个 <值,值所在下标> 的字典
这样可以快速判断

public int[] twoSum(int[] nums, int target) {
        int [] res= new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0;i<nums.length;i++){//构造<值，下标>的Map，用于快速检索
            map.put(nums[i],i);
            //注意：
            //这里会对重复值进行覆盖，取最后一个。
            //由于题目说明结果唯一，而下面的遍历是从前到后的，故这个覆盖不影响结果.
        }
        for (int i=0;i<nums.length;i++){
            if (map.get(target-nums[i])!=null){ //对于一个值a，判断target-a存不存在
                res[1] =map.get(target-nums[i]);//如果存在，还需要排除自身。
                if (res[1]!=i){
                    res[0]=i;
                    break;
                }
            }
        }
        return res;

分析：

执行用时 :3 ms, 在所有 Java 提交中击败了93.04%的用户
内存消耗 :41.9 MB, 在所有 Java 提交中击败了5.11%的用户
时间复杂度：HashMap基于链表散列，如果冲突较少，查询的时间复杂度视为O(1), 这里数组的长度应该不算长，于是时间复杂度视为 O(N)
空间复杂度: O(N)

其他解法

看了下其他人的题解，发现上面的我的第二种解法有很大的优化空间：
不用全部构造HashMap，有可能在构造过程中就已经出现了结果。

    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i])){
                indexs[0] = i;
                indexs[1] = hash.get(nums[i]);
                return indexs;
            }
            // key:补数，value：下标
            hash.put(target-nums[i],i);
        }
        return indexs;
    }
/*
这个方法很好，写法还有点不好理解：
遍历数组，每次都会向hashmap中加入一次，注意加入的是<补数,下标>
然后每次都会判断是否存在满足的结果，存在就返回，后面的不用再管了。
比如，[1,2,3],target=3
- 1：加入{2:1}
- 2: 存在key=2，返回，结束。

注意： 先判断并返回，后put
这是为了防止 如果当前数是target的1/2时会出错。比如 {[3,4],6}, 如果加入了6-3=3,再判断数组第一个3就会返回，出错！
*/