LeetCode第一题 “两数之和” 从无到有

1. 两数之和

题目来源：力扣（LeetCode）
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

补全代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {

    }
}

不论是学习，刷题，考试，面试。其实都有一个定律，无答案 < 复杂答案 < 简单正确答案。

我们刷LeetCode时也可以根据这个套路走。没有一口吃成胖子的人，所有的东西都是一步步进化而来。

简单思路

看到题目，我们脑子里大概有了些思路，看到结果我们知道一定要返回一个新数组，那。。。

int[] newNums= new int[2];
//TODO
return newNums;

这个两行代码坑定是有的。也就是最后得到的两个值要放到这个新的newNums数组中。现在要做的是求这个两个数。

我们就按我们自己的思路来，我拿nums第一个数和剩余的所有数各自相加如果等于target，那不就找到了吗？如果没有，那就走第二步，拿第二个数和剩余的数各自相加。。。直到找到，或者走完所有的数。

代码实现:

public int[] twoSum(int[] nums, int target) {
    int[] newNums= new int[2];
    //第一次拿的数
    for (int i = 0; i < nums.length; i++) {
        //第二次拿的数
        for (int j = i + 1; j < nums.length; j++) {
            //如果两个相等则向newNums赋值退出
            if (nums[i] + nums[j] == target){
                newNums[0] = i;
                newNums[1] = j;
                break;
            }
        }
    }
    return newNums;
}

这就是现实了，那开始改进吧！

进阶

我们可不可以用java里现成的工具类呢？list里面好像有个contains()方法可以帮我们找元素，我们那就不用遍历了好像。
思路：我们用target减去第一个元素得到一个结果，然后在剩余的list里面查找是否包含这个结果那不就对了吗？不包含就往下走。额。。。好像需要创建好多list,有什么好办法吗？

有了！

我把的到的结果放到list里面只要在循环开始的时候判断元素是不是在结果里面，在的话不就找到了吗？结果所在的位置就是开始的元素。

代码实现:

public int[] twoSum1(int[] nums, int target) {
    int[] newNums= new int[2];
    List<Integer> list = new ArrayList<>();
    //第一次拿的数
    for (int i = 0; i < nums.length; i++) {
        //看看是否包含
        if (list.contains(nums[i])) {
            newNums[0] = list.indexOf(nums[i]);
            newNums[1] = i;
            break;
        }
        //不包含把结果放到list里面
        list.add(target - nums[i]);
    }
    return newNums;
}

实现是实现了，但是这效率。。。进阶失败。为什么呢？
分析原因:
这地方好像是用来list的contains和indexOf方法了，我们看下源码怎么实现的。

源码
contains

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

indexOf

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

。。。 找到原因了，我里外里循环了三次，肯定比第一次慢多了。那没有好的办法了吗？

再次进阶

list的contains不行，那hashMap的contains，这个方法的时间复杂度应该是O(1)，试试吧。思路和list思路相同，只是把key的的位置放结果，value的位置放元素的位置。

代码实现:

public static int[] twoSum2(int[] nums, int target) {
    int[] newNums= new int[2];
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    //第一次拿的数
    for (int i = 0; i < nums.length; i++) {
        //看看是否包含
        if (hashMap.containsKey(nums[i])) {
            newNums[0] = hashMap.get(nums[i]);
            newNums[1] = i;
            break;
        }
        //不包含把结果放到list里面
        hashMap.put(target - nums[i], i);
    }
    return newNums;
}

哇，这个速度，应该应该可以完结撒花了吧，🎉🎉🎉。