数组两数之和的算法
Ⅰ、数组两数之和算法的方案一：1、题目描述：2、解题思路：3、实现代码：
Ⅱ、数组两数之和算法的方案二：1、实现代码：
Ⅲ、小结：
Ⅰ、数组两数之和算法的方案一：
1、题目描述：
给定⼀个整数数组 nums 和⼀个⽬标值 target，请你在该数组中找出和为⽬标值的那 两个 整数，并返回他们的数组下标； 你可以假设每种输⼊只会对应⼀个答案；但是，数组中同⼀个元素不能使⽤两遍； 示例1: 给定 nums = [2, 7, 11, 15], target = 9; 因为 nums[0] + nums[1] = 2 + 7 = 9; 所以返回 [0, 1] 示例2: 给定 nums = [2, 3, 5, 6, 11, 15], target = 8; 因为 nums[1] + nums[2] = 3 + 5 = 8; 所以返回[ 1, 2 ]
2、解题思路：
方案一： 对于这道题，我们很容易想到使⽤两层循环来解决这个问题，但是两层循环的复杂度为O（n2），但也能解决该问题，当然，我们也可以考虑能否换⼀种思路，减⼩复杂度。
方案二： 这⾥使⽤⼀个 map 对象来储存遍历过的数字以及对应的索引值； 我们在这⾥使⽤减法进⾏计算： ● 计算 target 和第⼀个数字的差，并记录进 map 对象中，其中两数差值作为 key，其索引值作为 value。 ● 再计算第⼆个数字与 target 的差值，并与 map 对象中的数值进⾏对⽐，若相同，直接返回，若没有相同值，就将这个差值也存⼊ map 对象中。 ● 重复第⼆步，直到找到⽬标值。
3、实现代码：
其一、代码为：
// 双层循环的代码执行过程：
const twoSum = (nums, target) => {
let len = nums.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (nums[i] + nums[j] == target && i != j) {
return [i, j]
}
}
}
}
// 此时的输出结果为：[ 1, 8 ];
twoSum([1, 2, 3, 4, 11, 15, 22, 78, 7], 9)
执行 twoSum([1, 2, 3, 4, 11, 15, 22, 78, 7], 9) 函数后代码执行的过程：
第一个循环：for (let i = 0; i < len; i++) {}, len = 9, i=0 的情况：
第二个循环：for (let j = 0; j < len; j++) {}, len = 9, target = 9;
i j num[i] num[j] nums[i] + nums[j] == target && i != j
0 0 num[0]=1 num[0]=1 false
0 1 num[0]=1 num[1]=2 false
0 2 num[0]=1 num[2]=3 false
0 3 num[0]=1 num[3]=4 false
0 4 num[0]=1 num[4]=11 false
0 5 num[0]=1 num[5]=15 false
0 6 num[0]=1 num[6]=22 false
0 7 num[0]=1 num[7]=78 false
0 8 num[0]=1 num[8]=7 false
第一个循环：for (let i = 0; i < len; i++) {}, len = 9, i=1 的情况：
第二个循环：for (let j = 0; j < len; j++) {}, len = 9, target = 9;
i j num[i] num[j] nums[i] + nums[j] == target && i != j
1 0 num[1]=2 num[0]=1 false
1 1 num[1]=2 num[1]=2 false
1 2 num[1]=2 num[2]=3 false
1 3 num[1]=2 num[3]=4 false
1 4 num[1]=2 num[4]=11 false
1 5 num[1]=2 num[5]=15 false
1 6 num[1]=2 num[6]=22 false
1 7 num[1]=2 num[7]=78 false
1 8 num[1]=2 num[8]=7 true
执行 return [i, j] 语句后，页面的返回值为：[1,8]
其二、截图为：
Ⅱ、数组两数之和算法的方案二：
1、实现代码：
其一、代码为：
// 通过 map 对象来储存遍历过的数字以及对应的索引值，通过减法来计算：
const twoSum = (nums, target) => {
// let array = []
const maps = {}
const len = nums.length
for (let i = 0; i < len; i++) {
// console.log(maps[target - nums[i]], 11223344)
if (maps[target - nums[i]] !== undefined) {
return [maps[target - nums[i]], i]
// array.push([maps[target - nums[i]], i])
}
maps[nums[i]] = i
// console.log(maps, 5566778899)
}
// return array
}
// 此时的输出结果为：[ 1, 8 ];
twoSum([1, 2, 3, 4, 11, 15, 22, 78, 7], 9)
执行 twoSum([1, 2, 3, 4, 11, 15, 22, 78, 7], 9) 函数后代码执行的过程：
第一个循环：for (let i = 0; i < len; i++) {}, len = 9, target = 9 的情况：
i maps[target - nums[i]] maps[nums[i]] = i maps
0 maps[8]=undefined maps[1]=0 {1:0}
1 maps[7]=undefined maps[2]=1 {1:0,2:1}
2 maps[6]=undefined maps[3]=2 {1:0,2:1,3:2}
3 maps[5]=undefined maps[4]=3 {1:0,2:1,3:2,4:3}
4 maps[-2]=undefined maps[11]=4 {1:0,2:1,3:2,4:3,11:4}
5 maps[-6]=undefined maps[15]=5 {1:0,2:1,3:2,4:3,11:4,15:5}
6 maps[-13]=undefined maps[22]=6 {1:0,2:1,3:2,4:3,11:4,15:5,22:6}
7 maps[-69]=undefined maps[78]=7 {1:0,2:1,3:2,4:3,11:4,15:5,22:6,78:7}
8 maps[2]!==undefined
执行 return [maps[target - nums[i]], i] 语句(即：return [map[2],8])后，页面的返回值为：[1,8]
注意：maps[2] 并不代表着 maps 是一个数组，而是 maps 对象取属性值的另一种语法(即：同 maps.2 的用法，但数字一般不支持而是
支持maps[2] 这样的语法);
当然，也可以修改该代码，如上述代码，放开注释就可以得到符合 target 值的二维数组，如：[ [ 1, 8 ] ];
其二、截图为：
Ⅲ、小结：
其一、哪里有不对或不合适的地方，还请大佬们多多指点和交流！ 其二、若有转发或引用本文章内容，请注明本博客地址(直接点击下面 url 跳转) https://blog.csdn.net/weixin_43405300,创作不易，且行且珍惜！ 其三、有兴趣的话，可以多多关注这个专栏(Vue(Vue2+Vue3)面试必备专栏)(直接点击下面 url 跳转)：https://blog.csdn.net/weixin_43405300/category_11525646.html?spm=1001.2014.3001.5482
推荐文章
您阅读本篇文章共花了：
发表评论