给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1.简单粗暴,时间复杂度什么的都不要考虑
var twoSum = function(nums, target) {
var newArr = [];
for(let i = 0; i<nums.length; i++){
for(let j = i+1; j<nums.length; j++){
if(nums[i] + nums[j] === target){
newArr.push(i,j);
}
}
}
return newArr;
}
2.排序,先将数组排序,将数组从前向后排序,时间复杂度(nlogn)
while(nums[i] + nums[j] != target){
if(nums[i] + nums[j] > target){
j--;
}else{
i++;
}
}
完整代码
var twoSum = function(nums, target) {
var temp = nums.slice(0);
nums = nums.sort(function(a,b){return a-b;});
var i = 0;
var j = nums.length - 1;
while(nums[i] + nums[j] != target){
if(nums[i] + nums[j] > target){
j--;
}else{
i++;
}
}
console.log(i);
console.log(j);
i = temp.indexOf(nums[i]);
console.log(i);
j = temp.lastIndexOf(nums[j]);
var index = new Array(i, j);
console.log(temp);
console.log(nums);
console.log(index);
index = index.sort(function(a,b){return a-b;});
return index;
};
3.终极版,,,采用数组下标。
var twoSum = function(nums, target) {
var temp = [];
for (var i = 0; i < nums.length; i++) {
var cur = nums[i];
if (temp[target - cur] !== undefined) {
return [temp[target - cur], i];
}
temp[cur] = i;
}
return [];
};