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

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

给定一个整数数组 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<Integer,Integer> hash = new HashMap<Integer,Integer>();
    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;
}

其中巧妙的地方：

再来看看运行结果：

看看两个算法对比：

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

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