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

  • 作者: 凯哥Java
  • 算法刷题
  • 时间:2019-08-09 13:07
  • 1876人已阅读
简介 给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。示例:给定nums=[2,7,11,15],target=9因为nums[0]+nums[1]=2+7=9所以返回[0,1].这个题目是不是很简单啊。首先,我们想到的第一种方案就是for循环。嵌套循环。如下:

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

给定一个整数数组 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;
}

运行结果:

a31f9d367f105622468728959fd40c1b.png

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

f4976f9f42f0a8dd4ecd8a43b8f16206.png

是不是很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;
}

其中巧妙的地方:

f26ec04957bb6939f2b89a7cade76b66.png

再来看看运行结果:

c17fb7dfbe2227becc7db56d498be764.png

看看两个算法对比:

231c56bcd07165cfe6239de7adce2ded.png

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

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

Top Top