[数据结构与算法] 【透过算法了解编程】之两数之和

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【透过算法了解编程】之两数之和 -> 正文阅读

[数据结构与算法]【透过算法了解编程】之两数之和

介绍：

大家好，我是猿码叔叔，很高兴又和大家见面了。

细数进入 Java 领域这几年，可谓一波三折，体会过求职与加班的心酸之后，也渐渐的开始学会将行业与自身职业素养联系起来，去思考如何做自己的职业规划。

技术似乎永远也是一个解不开的谜底，无论你怎么赴汤蹈火，最终都只有一个归宿，那就是家庭。所以啰嗦一句，我们学习技术，热爱技术最终都是为了有一个好的家庭。

正题：

今天要写的算法是力扣中的第一道题《两数之和》。

难度：容易

题目内容：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

题目来源：力扣

💡分析：

根据题意，假设： $nums[i]$ + $nums[j]$ ?== $target$ ，

则有? $target$ -? $nums[i]$ == $nums[j]$ ?, ? $target$ ?-? $nums[j]$ ==?? $nums[i]$ ?

因此，最简单的办法就是全局搜索。我们分别创建 2 个 $for$ 循环。 $for_{_{1}}$ ?代表 $nums[i]$ ,?

? $for_{2}$ ?代表 ? $nums[j]$ ?，这样一来我们将两个循环的当前下标元素进行相加，如果等于 $target$ ，就按照题目要求的方式返回即可，反之继续遍历。由于题目中强调，数组 $nums$ ?中一定会有一对满足要求的数对，且答案只有一个。因此我们不用担心是否有别的答案会出现，或者没有答案的情况。

?我们先用简单的方式实现一下，代码如下：

    public int[] twoSum1(int[] nums, int target) {
        int n = nums.length;
        // 定义存储结果的数组
        int[] res = new int[2];
        for (int i = 0; i < n; i++) {
            // 假设 nums[i] 为 target 的减数
            int sub = target - nums[i];
            for (int j = 0; j < n; j++) {
                // 判断当前 nums[j] 是否为 nums[i] 的差
                if(sub == nums[j]) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }

时间复杂度： $O(n^{^{2}})$ ， $n$ 为输入数组中元素的数量

空间复杂度： $O(1)$

💡 思考

这道题，很容易引人思考的一点是，当我们假设 $nums[i]$ ?为减数时，必然能根据假设获取到差值，因此我们可以用空间来换时间，使用 hash 来解题。当然，这里我不使用 HashMap，因为 HashMap 是一个封装的散列表，底层也会使用数组扩容机制来 hash 数据，因此我们来学习一下数组 hash。但前提是 $nums[i]$ ? 尽可能的小，且大于 $0$ 。

假设: $1 <= nums[i] <= 1000$ ;

为了降低时间复杂度，我们必须尽可能少的去对 nums 进行全局搜索。而且我们知道， $nums[i]$ 最多为 1000，因此我们使用 $nums[i]$ ?本身作为 hash 值（索引），能快速定位到其是否存在。初始化的数组，元素都会为 0。

设数组： $int[] hash = new int[1001]$ ;? 若?? $hash[target - hash_{i}]$ ?> 0，说明该差值存在。

下面是代码实现：

    public int[] twoSumHash(int[] nums, int target) {
        int n = nums.length;
        // 用以存储索引的 hash 数组
        int[] hash = new int[1001];
        for (int i = 0; i < n; i++) {
            // 用元素值代替 hash 数组的索引
            hash[nums[i]] = i;
            // 求差值
            int sub = target - nums[i], idx;
            // 避免数组越界
            if(sub > -1) {
                // 如果 sub 定位到的 hash 数组元素不为 0，
                // 意味着以该元素为下标的值即为差值的索引
                if((idx = hash[sub]) > 0 && idx != i) {
                    return new int[] {i, idx};
                }
            }
        }
        return new int[0];
    }

时间复杂度： $O(n)$ ， $n$ 为输入数组中元素的数量

空间复杂度： $O(n)$

当然，这中解法只能作为数组 hash 的一种示范，并不能解决所有情况下的两数之和。

大家可以尝试自己去用 HashMap 实现，与写法 2 差不多。

🎓 总结：

这道题，可以很好的作为理解 hash?实现原理的辅助，同时也颠覆我们对数组查询效率较低的认知，也渗透出算法为解决诸多难题要面对的最大困难之一 —— 搜索。比如 Elasticsearch就用到了 D-Gap 索引算法，来压缩文档编号，达到空间压缩的作用。可能这些效率上的提升是细微的，但对于庞大的数据量来说，足够了。算法之所以区别于一般的程序，我个人认为它更多的是以效率为导向，来快速解决问题。

学习点：