算法经典题《两数之和》

大家好，欢迎来到IT知识分享网。

最近开始刷算法，这道题算是算法入门的第一道题也是比较经典的题，我说说我个人的理解：

题意大概是，给你一个整数数组，再给一个目标数，找出数组中两个数之和对应目标数的下标，且下标不能相同。

看见道题，第一时间想了第一种暴力激活成功教程的办法，是最基础的o(n²)的解决办法：这也是大部分人第一时间想到的解题方案，利用两层for循环了来解题，暴力解决了但是效率比较低，提交上去效率感人

执行耗时:110 ms,击败了5.05% 的Java用户
内存消耗:38.7 MB,击败了23.81% 的Java用户

int[] arr = new int[2];
for (int i = 0; i < nums.length; i++) {
    for (int k = 0; k < nums.length; k++) {
        if (k !=i && nums[i] + nums[k] == target) {
            arr[0] = i;
            arr[1] = k;
        }
    }
}

考虑过后，发现虽然是o(n²)，解题方法但是可以对其进行优化，首先第两层循环不需要都循环到结束才返回，可以找到数就可以直接返回节省了查找的时间，第二点、基与下标不能相同，二层循环开始就可以不用和自己匹配，且上层循环匹配过的数也没有必要反复配一次，基于这两点又进行了一次优化，代码如下

执行耗时:55 ms,击败了26.64% 的Java用户
内存消耗:38.7 MB,击败了22.56% 的Java用户

 int[] arr = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int k = i + 1; k < nums.length; k++) {
                if (nums[i] + nums[k] == target) {
                    arr[0] = i;
                    arr[1] = k;
                    break;
                }
            }
            if (arr[1] != 0) {
                break;
            }
        }

这次改动，改动后发现效率提升了一倍，效率依旧感人，但是始终是o(n²)的解题方案，始终桎梏在数组的解题方案上，后来参考了网上大佬的优解思路，想出了第三种解题的方法

第三种解题的方案，是彻底放弃了数组的解题方案，由于数组始终需要移动到值的下标位置上，才能进行值匹配，从头到尾需要大量的时间逐一比对，这个数据结构决定了它的效率的上限，第三种思路，就是利用HashMap的数据结构，已知HashMap

的底层是基于k和v键值对的匹配方法，HashMap根据键来查询对应的值的时候类似通过，字典目录找对应的页，效率就比遍历数组快很多，代码如下

执行耗时:2 ms,击败了86.61% 的Java用户
内存消耗:38.7 MB,击败了37.28% 的Java用户

HashMap<Integer, Integer> arrMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    if (arrMap.containsKey(target - nums[i])) {
        return new int[]{arrMap.get(target - nums[i]), i};
    }
    arrMap.put(nums[i], i);
}
return new int[2];

总结，一道简单两数之和，里面有这么多的门道，不同的处理方法和速度差距几十倍，对于数据的处理用好了算法，效率提升非常的巨大，非常建议想要深入了解算法的朋友，可以去学习下《数据结构》。