题目：Two Sum 两数之和

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

示例:

  1. 给定 nums = [2, 7, 11, 15], target = 9
  2. 因为 nums[0] + nums[1] = 2 + 7 = 9
  3. 所以返回 [0, 1]

思路分析

说到查找数据，我们一般想到的就是顺序查找法和二分查找法，但是这两种都需要多次循环才能查找到值，能不能通过一次循环就找到呢？
这道题的关键在于检索数组中是否存在当前值与target的差值，所以我们需要检索迅速的数据结构，首先想到的就是HashMap和ArrayList。同时我们在迭代过程中需要保存下标信息，所以我们排除ArrayList，选用HashMap。

Java 解法一：HashMap（拉链法）

遍历数组，每次遍历的时候判断差值是否在hashmap中，如果不存在则保存当前数的值为key，下标为value以供查找。如果存在，则返回map中的下标和当前遍历对象的下标。

public static int[] twoSum(int[] nums, int target){
    HashMap<Integer, Integer> m = new HashMap<>();
    int[] res = new int[2];
    for (int i = 0; i < nums.length; ++i) {
        int t = target - nums[i];
        // 如果差值已经存在，结束循环，返回结果
        if (m.containsKey(t)) {
            // map中存在差值，返回下标数组
            res[0] = m.get(t);
            res[1] = i;
            break;
        }
        //否则将差值放入hashmap作为key，下标作为val
        m.put(nums[i], i);
    }
    return res;
}

时间复杂度：O(1) ~O(n)

通过以空间换取速度的方式，我们可以将查找时间从 O(n)O(n) 降低到 O(1)O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现hash冲突，查找用时可能会退化到 O(n)O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)O(1)。
image.png
HashMap的hashcode原理可以参考https://www.yuque.com/mygod/bhwzdi/zb72bk#975ec638

LeetCode用时：3ms

image.png

Java 解法二：int[] （直接寻址法）

从上面一种解法得到思路，数组同样是一个检索非常快速的数据结构，保存当前数值与11111111111逻辑与作为key，下标+1作为value，即可实现以上需求。同样基于hash的运用，这个查找方式的优点是以空间换时间，设定好大小后性能会优于HashMap；

public static int[] twoSum(int[] nums, int target) {
    // 定义一个2048大小的数组
    int volume = 2<<10; //2048
    int bitNum = volume-1; //11111111111
    int[] res = new int[volume];
    for(int i=0;i<nums.length;i++){
        // 计算当前数值的hash， 按位与上11111111111得到res数组的下标
        int hash = nums[i] & bitNum;
        // 计算差值的hash
        int thash = (target-nums[i])&bitNum;
        // 如果用差值的hash取不到值，将当前数字的hash作为key，下标作为val存入工具数组res
        if(res[thash] == 0){
            // 这里之所以要+1，是因为数组的默认值是0,如果存入i那么nums的第一个元素的坐标就不会存进去
            res[hash] = i+1;
        } else {
            // 如果去到了，说明之前存入过需要的差值，取出得到结果
            return new int[]{res[thash]-1,i};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

时间复杂度：O(1)

只要一次查询就能返回数据

LeetCode用时：0ms

image.png

hash原理：

由于数组长度是2的N次幂，所以lenth-1就相当于与11111低位掩码，与h逻辑与后保留h的低位，既待插入node在数组中的位置) 逻辑&的字节码比%求模少很多，速度更快。

缺点：

1）浪费空间，⽐如 1,5,7,6,3,4,8,12306 ，最⼤值12306 ，按照上述⽅式需要定义⼀个⽐如⻓度为12307的数组，但是只存储零星的⼏个数据，其他位置空间都浪费着
2）数据如：1,5,7,6,3,4,8,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2最⼤值12，⽐如开辟13个空间，存储不了这么多内容
3）这里只是用了简单的hash算法，没有加上扰动函数，所以hash性能较差，且没有对hash冲突的情况做处理，数值较大或者数组容量太小时，产生的hash冲突会导致函数错误

顺序查找法（暴力不推荐）

暴力法很简单，遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素。

public static int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

时间复杂度：O(n^2)

对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)

Letcode用时：68ms

image.png