两数之和-力扣第1题完整解析（Java）

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

方法一：暴力枚举

代码如下，通过双层循环，在数组中依次遍历查找两数之和为目标值target的数组元素，需要注意i是从下标为0的位置开始循环，j不能与i重复查询，故j设置为从下标为1的位置开始循环，此方法的时间复杂度为O（）。

class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0,j = 0,s[];
for(i=0;i<nums.length;i++){
for(j=i+1;j<nums.length;j++){
if(nums[i]+nums[j] == target){
return new int[]{i, j};
}
}
}
return new int[0];
}
}

方法二：哈希表法

科普一下什么是哈希表，首先介绍一下哈希函数，哈希函数是一种根据函数和查找关键字key，直接确定出查找值所在位置的函数，而哈希表则是基于哈希函数所建立的一种查找表，它是由数组和链表组成的，通过键值对的方式存取数据，即【key,value】,通过哈希函数，它将key转换成对应的数组下标。

思考一下，方法一的暴力枚举法的时间复杂度之所以高，是因为代码中嵌套两层循环去遍历数组，那么有没有什么方法只需要遍历一次数组就可以得到最终的结果呢？分析可知，按照暴力枚举的思路，我们需要在数组中既找出num[i],又要找出num[j],然后才能判断两者之和是否等于target。

简化一下思维方式，其实我们也可以只遍历一次数组，得到每次数组下标为i处的元素的值，然后判断数组中是否包含某个元素满足：target-num[i]==num[j]即可。

因此，我们可以先创建一个哈希表，对于每一个num[i],去判断哈希表中是否有元素的值等于target-num[i]，然后将num[i]的值插入哈希表中，这样就可以保证元素不会和自身匹配。搞清逻辑之后，下面来看一下代码实现。

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}

此时的时间复杂度为：O（n）。