乐趣区

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

题目形容

给定一个整数数组 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.includesarr.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% 了。

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

退出移动版