数组：两数之和两数之和

69 阅读 0 评论 46 点赞

我是靠谱客的博主感动镜子，最近开发中收集的这篇文章主要介绍数组：两数之和两数之和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

两数之和

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

示例一：
      输入： nums = [2,7,11,15] ，target = 9
      输出：[0,1]
      解释：因为nums[0] + nums[1] == 9，所以返回 [0,1]

思路一：暴力法。时间复杂度O（n²），空间复杂度O(1)

使用两个for循环，每个元素之间相互比较，若两元素之和等于target，返回两元素的下标。

假设target==24

图示：
在这里插入图片描述
       ar[i] +ar[j] == 9，不满足，j向后移，如下图：

       ar[i] + ar[j] == 13，不满足，j向后移，如下图：

      ar[i] + ar[j] == 15，不满足，此时，第一个元素，已经和数组内其他元素全部相加完成了，所以，该让数组第二个元素和数组中其他元素相加，看是否能得到target，如下图：
在这里插入图片描述
      注意，此时 j 并没有从数组第一个元素开始，这是由于第二个元素已经和第一个元素相加过了，在这里，我们就必须要再想加一遍了。

直到，i 和 j 分别指向如下图所示时，返回 i 和 j 。
在这里插入图片描述
此时ar[i] + ar[j] == 24 == target，此时，i和j就是我们要寻找的下标。

代码实现:

public static int[] getTwoSumIndex(int[] ar,int target){
int[] tag = new int[2];
for (int i = 0; i < ar.length; i++) {
for (int j = i+1; j <ar.length ; j++) {
if (ar[i]+ ar[j] == target){
tag[0] = i;
tag[1] = j;
}
}
}
return tag;
}

思路二：使用哈希表

对数组进行预处理，将数组中所有元素及对应的索引放入HashMap中。通过遍历数组，在map中寻找target-x，如果找到了，说明数组中存在两个数相加等于target，如果不存在，返回null。

target - x 计算出哪个数能跟当前的数字(ar[i])相加得到target。

代码实现:


// 时间复杂度：O(2n)
// 空间复杂度：O(n)
public static int[] towSum(int[] arr,int target){
// 使用哈希表
// 数据预处理： 将数组中的每个元素及对应的下标存储到哈希表中
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i],i);
}
// 遍历数组判断是否存在两数相加与target相等的
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
if (map.containsKey(target - x)){
Integer index= map.get(target - x);
// 确保i和index不是同一元素，类似于{2,2,1}，如果target为4，输出[0,1]，而不是[0,0]
if (index!=i){
return new int[]{i,index};
}
}
}
return null;
}

对哈希表的优化，上面使用了两次for循环，我们使用一次for循环能不能达到效果呢？当然可以，我们可以把上面中的预处理操作去掉，将预处理操作和判断操作放入一个for循环中，先判断map集合中是否包含相应的值，再将每次遍历得到的数据放入map集合中。

// 时间复杂度O(n)
// 空间复杂度O(n)
public static int[] toSum2(int[]arr,int target){
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
if (map.containsKey(target-x)){
Integer index = map.get(target - x);
return new int[]{i,index};
}
map.put(x,i);
}
return null;
}