两数之和

声明：本篇文章除部分引用外，均为原创内容，如有雷同纯属巧合，引用转载请附上原文链接与声明。
注:本文若包含部分下载内容，本着一站式阅读的想法，本站提供其对应软件的直接下载方式，但是由于带宽原因下载缓慢是必然的，建议读者去相关官网进行下载，若某些软件禁止三方传播，请在主页上通过联系作者的方式将相关项目进行取消。

文章大纲

题目

暴力法

哈希表遍历

一.题目

名称：两数之和
序号：1
描述：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
假设：每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
来源：LeetCode。
难度：简单
即实现以下方法：

    /**
     * @param nums 输入的数组
     * @param target 目标值
     * @return 返回满足需求的数组索引组成的数组
     */
    public int[] twoSum(int[] nums, int target)

二.暴力法

首先最开始能想到的是两次轮询数组的方式来求得输出，即暴力法。代码如下

    public 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[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("no solution");
    }

实现方式: 通过对每一个元素进行轮询，然后再轮询剩下的元素，通过以上操作得到答案，这也是最简单的最简单的方式。
时间复杂度: O(n²)
空间复杂度: O(1)

三.哈希表遍历

3.1 两次遍历
首先思考，除了遍历的方式，需要快速获取值的方式是通过散列的方式来实现，如果我们将数组通过哈希表的方式存储在哈希表中，那么只要可以获取到值，既可以迅速定位到值对应的索引。代码如下。

    public int[] twoSum(int[] nums, int target) {
        // k:value, v:index
        Map<Integer, Integer> container = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            container.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (container.containsKey(diff)) {
                return new int[]{i, container.get(diff)};
            }
        }
        throw new IllegalArgumentException("no solution");
    }

实现方式:

首先将数组缓存在哈希表container中，将数组项的值作为key，索引作为value。这样做可以通过值获取到对应的索引
遍历数组中的每一个元素，计算和target的差值，通过哈希表container.containsKey()这个复杂度为O(1)的方法检查是否存在满足条件的值。
存在即获取到指定的索引，其操作也是O(1)的。

复杂度分析：由于第一次遍历数组是为了将值缓存在哈希表中，其复杂度为O(n),第二次遍历是为了得到结果，复杂度也为O(n)。而在空间上多采用了哈希表来预缓存数组，改变数组的存储方式。空间多占用了O(n)

时间复杂度: O(n) + O(n) = O(n)
空间复杂度: O(n)

3.2 一次遍历
就两次遍历而言，其思想类似于暴力法，均是针对当前轮询到的值和剩下的全部值进行匹配，直到匹配到符合要求的值即可。区别是在于暴力法在与剩下的全部值进行匹配的时是采用的轮询的方式，因为其无法像哈希表那样通过值在O(1)的限制内直接获取其索引，所以导致了暴力法的时间复杂度是O(n²) 而二次遍历由于其与剩下值匹配这一步是O(1)的，所以复杂度是O(1)。

现在我们换一种思路，虽然这里也是使用的哈希表，但是其解决实想与前两种不一样。我们在对一个值进行轮询的时候，在选取第二个值的时候，可以将剩下的值分为两个部分

在哈希表中
不在哈希表中
那我们设计出来如下流程，并实现如下代码

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> container = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (container.containsKey(diff)) {
                return new int[]{i, container.get(diff)};
            }
            container.put(nums[i], i);
        }
        throw new IllegalArgumentException("no solution");
    }

这段代码是实现的逻辑流程为

依次遍历输入的数组
遍历其中每一个值的时候，从哈希表中尝试获取其目标差值
如果获取到了则直接返回
如果未获取到，则将该值和索引放入到哈希表中，然后对下一个值进行一样的操作

这里可能不太好理解这里是如何实现上文所说的思路，可以简单地理解为：当遍历到某一个值(a)的时候，如果所需要的值(b)在哈希表中不存在，那么如果存在的话只能在哈希表外，而且该值被加入到了哈希表中用于接下来其他值的遍历和匹配。当遍历上次遍历所需要的值(b)时，所需要的值(a)肯定在哈希表中即可匹配到。这样针对数组每一个值，采用上述方式即可得到结果。

复杂度分析：整个流程仅轮询了一次数组，所以时间复杂度是O(n)，采取了哈希表额外存储数组，所以空间复杂度是O(n)
时间复杂度: O(n)
空间复杂度: O(n)

3.3 双指针 + 排序
看到该问题的相关解答上还存在该解法，但这种解法从本质上仍然是暴力法。只是通过排序和双指针的方式，减少了数据扫描的范围，但是并不是数量级上的优化。所以这里就不再赘述了。