力扣刷题第一题两数之和
题目要求
解题
方法一(常规解法)
遍历数组
当为第一个数的时候,从后面找有没有和他相加得结果的数
如果有就返回下标
JS代码
var twoSum = function(nums, target) {
let data = [];
let k = 0;
for(let i = 0;i<nums.length;i++){
for (let j = i + 1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
data[k] = i;
data[k+1] = j;
k++;
i=j;
}
}
}
return data;
};
或者
var twoSum = function(nums, target) {
let c = [];
for (let index of nums.keys()){
if(c.indexOf(nums[index])>=0){
return [c.indexOf(nums[index]),index]
}
else{
c.push(target-nums[index]);
}
}
}
方法二(速度快)
思路:
既然我们要找一对数,且这一对数的和Y是确定的,那么我们知道X就可以知道需要什么数(Y-X)
所以我们找的是(Y-X)但是遍历原数组比较慢且需要对比,如果建立一个新的对照表比如
我们有一个数组
arr = [1,3,4,2] 求出和target等于6的两数的下标
我们可以新建一个空数组arrN=[]用来存储target-value(当前遍历的arr数组的某个值,比如1也可以是3/4/2)
遍历arr的时候每次先从arrN中看看当前arr数是否存在于arrN
为什么呢,arr遍历第一次的时候 arrN为空,我们让arrN存储5 (6-1)
此时arrN=[5] 此时我们发现5在arrN中的下标是0,1在arr中的下标也是0
继续遍历arr此时遍历到值为3
我们用arrN.indesOf(3)来返回arrN中第一次出现3的下标,如果没有就返回-1,很显然arrN=[5]中并没有3,然后arrN存储3(6-3) 此时arrN=[5,3]
继续遍历arr此时遍历到值为4
我们用arrN.indesOf(4)来返回arrN中第一次出现4的下标,如果没有就返回-1,很显然arrN=[5,3]中并没有4,然后arrN存储2(6-4) 此时arrN=[5,3,2]
继续遍历arr此时遍历到值为2
我们用arrN.indesOf(2)来返回arrN中第一次出现4的下标,如果没有就返回-1,很显然arrN=[5,3,2]中有2,arrN.indesOf(2)返回了2,也就是2在arrN中的下标,此时我们也知道arr遍历到数组下标为3的元素
那么我们返回[2,3]就是题目所需结果
需要理解的是 我们往arrN中存数的时候,比如我们处理arr第一个数1,此时1的下标是0,那么我们的arrN开始存第一个数5(6-1),5在arrN中的下标也是0,5就是匹配下标为0的数所需的数,所以我们在后面找arr中的数是否存在于arrN中就行了。
当我们遍历到4的时候存储了2,遍历到2的时候,发现2存在于arrN中,且下标为2,2在arr中下标是3
所以返回[2,3]
代码如下
var twoSum = function(nums, target) {
let c = [];
for (let index of nums.keys()){
if(c.indexOf(nums[index])>=0){
return [c.indexOf(nums[index]),index]
}
else{
c.push(target-nums[index]);
}
}
};
或者
var twoSum = function(nums, target) {
let c = [];
for (let index of nums.keys()){
let a = c.indexOf(nums[index]);
if(a>=0){
return [a,index]
}
else{
c.push(target-nums[index]);
}
}
};
大学之道亦在自身,努力学习,热血青春
- 点赞
- 收藏
- 关注作者
评论(0)