力扣算法题

116 阅读 0 评论 77 点赞

我是靠谱客的博主风趣鸭子，这篇文章主要介绍力扣算法题，现在分享给大家，希望可以做个参考。

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
但是，数组中同一个元素不能使用两遍。

思路一：暴力枚举

将数组中的每个元素都拿来与后面的元素逐一相加，然后与目标值作比较，如果正确则直接返回下标值。
那么，就会有最坏的情况：循环遍历完数组的所有元素
代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var twoSum = function (nums, target) {
            // 输入不是一个数组 直接返回
            if (typeof nums !== 'object') return
            // 定义数组长度变量
            let length = nums.length
            for (let i = 0; i < length; i++) {
                for (let j = i + 1; j < length; j++) {
                    let sum = nums[i] + nums[j];
                    if (sum === target) {
                        return [i, j]
                    }
                }
            }
        }

思路二：利用es6语法新特性----MAP构造函数

MAP是JS的对象，本质属于键值对的集合，本质上可以作为是哈希表的实现，我们可以将第一个元素存入哈希表，循环遍历数组元素，得到所对应的目标差值，然后利用MAP构造函数的get()方法或者是has()方法得到其目标差值的key，即元素的下标值。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var twoSum = function (nums, target) {
            // 输入不是一个数组 直接返回
            if (typeof nums !== 'object') return
            // 定义数组长度变量
            let length = nums.length
            // 定义MAP构造函数的实例对象
            const MAP = new MAP()
            // 让第一个元素存入哈希表
            MAP.set(nums[0],0)
            // 开始循环遍历数组的元素 从第二个元素开始
            for (let i = 1; i < length; i++) {
               // 定义目标差值
               let other = target - nums[i]
               // 判断是否符合条件，返回对应的下标

                // get 方法读取 key 对应的键值，如果找不到 key ，返回 undefined
                // if (MAP.get(other) !== undefined) return [MAP.get(other), i]

                // 或者利用 has 方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。 
                if (MAP.has(other)) return [MAP.get(other),i]
                // 不符合的存入hash表
                MAP.set(nums[i], i)
              }
            }
        }