乐趣区

关于算法:力扣之两数之和

jiezi

题目形容

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

你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。

你能够按任意程序返回答案。

示例 1：

输出：nums = [2,7,11,15], target = 9
输入：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

示例 2：

输出：nums = [3,2,4], target = 6
输入：[1,2]

示例 3：

输出：nums = [3,3], target = 6
输入：[0,1]

力扣原题目地址：https://leetcode.cn/problems/…

咱们来看一下解决方案 …

四种计划，层层递进，次要还是思路 …

计划一，间接两层循环判断值是否相等

var twoSum = function (nums, target) {for (let i = 0; i < nums.length; i++) {
                        // j=i+ 1 即：下一项 == 以后项 +1 因为要一直和下一项相加看看是否等于 target
                        for (let j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [i, j]
                            }
                        }
                    }
                };

这种形式能够了解为暴力破解的形式，要循环两次工夫复杂度为 O(n) * O(n)即为 O(n²)，太慢了，咱们看看有没有优化形式

计划二，应用数组判断另一个值是否存在

思路：咱们曾经晓得两数之和的 target 了，同时在遍历的时候，也能拿到一个数 nums[i]，至于另外一个数，咱们能够总和减去一个数即：otherVal = target - nums[i]，而后再看看另外一个数otherVal 是否在这个数组外面，当然不能间接看，间接看又得循环一遍了，所以咱们能够新定义一个数组，把数组中的树一次追加进去，直到发现新数组中的某一项中有另外一个数，也就是说新数组中的这一项加上 nums[i] 刚好是等于target，这样的话，就实现工作了，代码如下：

var twoSum = function (nums, target) {let arr = [] // 1. 定义一个数组用来另存 nums 数组中的数据
                    for (let i = 0; i < nums.length; i++) { // 2. 循环失去每一项每个 一个数
                        let otherVal = target - nums[i] // 3. 通过一个数 计算出 另一个数
                        if (arr.includes(otherVal)) { // 4. 一开始数组中必定不蕴含另一个数
                            return [arr.indexOf(otherVal), i] // 6. 直到找到 
                        } else {arr.push(nums[i]) // 5. 不蕴含没事，那就存一份吧，不便后续匹配
                        }
                    }
                };

留神 arr 中的数组中的每一项，从左往右，是和 nums 数组中的每一项值以及索引是保持一致的，所以应用 arr.indexOf(otherVal) 找到的索引就是在 nums 中的索引

如果大家在力扣中依照这种形式提交的话，会发现这种形式的性能甚至还不如暴力破解的性能好呢！为何呢？起因是：arr.includes和 arr.indexOf 这两个办法都会遍历数组的，所以应用数组不是太好。那能不能应用对象呢？能够的，咱们来看看对象的写法

计划三，应用对象判断另外一个值是否存在

var twoSum = function (nums, target) {let obj = {} // 1. 定义一个对象用来另存 nums 数组中的数据
                for (let i = 0; i < nums.length; i++) { // 2. 循环失去每一项每个 一个数
                    let otherVal = target - nums[i] // 3. 通过一个数 计算出 另一个数
                    if (Object.values(obj).includes(otherVal)) { // 4. 一开始对象中的 value 数组必定不蕴含另一个数
                        // 6. values 数组值中蕴含这个数的话，就查找这个值所对应的索引即可
                        let k = (Object.values(obj)).findIndex((item) => {return item == otherVal})
                        return [k, i]
                    } else {obj[i] = nums[i] // 5. 不蕴含没事，就用对象存一份，对象的 key 是索引 i，对象的 value 是索引项 i 对应的值 nums[i]，如此不便后续匹配
                    }
                }
            };

思路和计划二应用数组的形式根本一样，都是通过差值，找找有没有另外一项，尽管能解决问题，然而这种写法是目前三种计划中最差的写法，因为应用了 Object.values、includes、findIndex 办法，所以效率非常低。提交力扣勉强可能通过，此处放上一张图，大家就通晓了

击败百分之五，基本上是倒数了，难堪，不过没事，咱们要得次要是思路

计划四，应用 Map 汇合判断另外一个值是否存在

首先，此计划是最优解，工夫空间复杂度都解决的不错，再说 Map 汇合的解决方案之前，咱们先来温习一下 Map 汇合的基本功能，以便于更好的了解后续代码

Map 常识的简略温习

let map = new Map() // new 实例化一个 Map 对象
// 增加 key value
map.set('name', '孙悟空')
map.set('age', '500')
map.set('home', '花果山水帘洞')
console.log(map.has('name'));// 是否存在 key 等于 name 的这个属性名 // true
console.log(map.get('name'));// 通过 key 去取其 value
console.log(map.has('score'));// 是否存在 key 等于 score 的这个属性名 // true
console.log('map 汇合', map);

咱们来看看打印进去的 ’map 汇合 ’ 的后果：


认真一下，呦，这 map 汇合和对象长得差不多啊。咱们能够简略的了解为 Map 汇合是非凡的对象存储模式，具体的了解 Map 汇合能够看一下 mdn 官网 https://developer.mozilla.org…

应用 Map 汇合存储数组数据

假如咱们有一个数组是：let nums = [19,24,25,28,30]

  • 咱们来看一下应用对象是如何模仿存储这个数据的
let obj = {
    0:19,
    1:24,
    2:25,
    3:28,
    4:30
}
// 应用对象存储，对象的 key 键就是数组的下标索引，对象的 value 值就是数组的索引值。当然数组也能够了解为是一种非凡的对象
  • 咱们再来看一下应用 Map 汇合来存储这个数组
let map = new Map()
map.set(0, 19)
map.set(1, 24)
map.set(2, 25)
map.set(3, 28)
map.set(4, 30)
console.log('map 汇合', map);

看看打印 ’map 汇合 ’：

这里肯定要反过来哦，数组的第 0 项是 19，能够 map.set(0, 19) 也能够 map.set(19, 0) 具体应用那种形式，看理论需要，本题目中应用 map.set(19, 0) 形式更加适合

好了，看到这里大家再看底下的具体代码，联合正文应该就更好了解了

Map 汇合解决两数之和问题代码

var twoSum = function (nums, target) {let map = new Map() // 1. 创立一个 map 汇合用来存储数据
    for (let i = 0; i < nums.length; i++) { // 2. 循环失去每一项每个 一个数
        let otherVal = target - nums[i] // 3. 失去另外一个值
        if (map.has(otherVal)) { // 4. 一开始必定是不存在的
            return [map.get(otherVal), i] // 6. 存在的话，就失去对应索引值，并返回
        } else {map.set(nums[i], i) // 5. 不存在就在 map 汇合存一份如：map.set(19, 0)
        }
    }
};

这种形式还不错，毕竟 Map 汇合的效率要高一些。留神辨别：数组形式、对象形式、以及 Map 汇合形式 它们的 判断是否存在、找索引 的区别形式，这一点很重要！

总结

对于两数之和的解法，其实还有别的形式，本文这四种形式，也只是抛砖引玉，给大家捋一下思路，毕竟工作中，有思路了，问题基本上就解决 80% 了。

好忘性不如烂笔头，记录一下吧^_^

退出移动版