每日一个小算法之两数之和

每日一个小算法之两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1].

这个题目是不是很简单啊。

本文出自凯哥Java(kaigejava)

首先，我们想到的第一种方案就是for循环。嵌套循环。如下：

JAVA代码：

public static void main(String[] args) {

Integer [] nums  = new Integer []{1,2,0,5,7,9,3};

Integer target  = 5;

Integer[] returnNums  = twoSum(nums,target);

System.out.println(JSON.toJSONString(returnNums));

}

public static Integer[] twoSum(Integer[] nums, Integer target) {

Integer[] returnNums = new Integer[2];

for (int i = 0; i < nums.length; i++) {

for (int j = i+1; j < nums.length; j++) {

int num1 = nums[i];

int num2 = nums[j];

if ((num1 + num2) == target) {

returnNums[0] = i;

returnNums[1] = j;

return returnNums;

}

}

}

return returnNums;

}

运行结果：

执行结果是出来了。我们看看执行时间：

是不是很low的一种方法。

那么接下来，我们看看第二中算法：

第二种算法和巧妙。Java代码如下：

private  Integer[] twoSum2(Integer[] nums, Integer target) {

Integer[] indexs = new Integer[2];

// 建立k-v ，一一对应的哈希表

HashMap 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]);

log.info(JSON.toJSONString(hash));

return indexs;

}

// 将数据存入 key为补数 ，value为下标

hash.put(target-nums[i],i);

log.info("==>:{},i=:{},target-nums[i]:{}",nums[i],i,target-nums[i]);

}

return indexs;

}

其中巧妙的地方：

再来看看运行结果：

看看两个算法对比：

再速度上是不是快了很多。

欢迎大家留下更好的算法。一起学习，一起成长

欢迎关注凯哥公众号：凯哥Java（kaigejava）

凯哥个人博客：www.kaigejava.com