从一个数组中找出两个元素相加等于目标数字，时间复杂度为O(n)

一、题目描述

从给定的数组中，找出两个元素相加等于目标元素，每个元素不能重复使用，并且时间复杂度等于O(n)

数组num[2, 3, 6, 1, 4, 7, 5, 1]
目标数为：7
输出：
[1, 6]
[2, 5]
[3, 4]

二、解题思路

1. 对数组进行升序排列
2. 设 i 从前开始往后加 1，设 k 从后往前减 1
3. 当下标为 i 的元素加上下标为 k 的元素小于目标元素，证明下标为 i 的元素太小，因为是升序排列，所以 i ++
4. 当下标为 i 的元素加上下标为 k 的元素大于目标元素，证明下标为 k 的元素太大，因为是升序排列，所以 k –
5. 当下标为 i 的元素加上下标为 k 的元素等于目标元素，将两个元素存入一个新的数组 tNum。由于每个元素不能重复使用，因此 i ++ , k - -
6. 返回数组 tNum
7. 两两输出 tNum中的元素

三、代码实现

var tNum = [];
//定义全局变量tNum数组
function search(num, target) {
var counter = 0;
num.sort(function(a, b) {
return a - b;
});
//将数组 num 进行升序排列
var k = num.length - 1; //声明 k 为数组的末尾下标
var i = 0;
//声明 i 为数组第一个元素的下标
while (i < k) {
if (num[i] + num[k] < target) {
i++;
//当前后两个元素相加小于目标元素时，将前面的元素往后遍历一位
} else if (num[i] + num[k] > target) {
k--;
//当前后两个元素相加大于目标元素时，将后面的元素往前遍历一位
} else {
//当两个元素相加等于目标元素时
tNum[counter] = num[i];
//将小的元素放入tNum数组
tNum[counter + 1] = num[k];
//将大的元素放入小的元素的后面一位
i++;
k--;
counter = counter + 2;
}
}
return tNum;
}
search([2, 3, 6, 1, 4, 7, 5, 1], 7);
for (var j = 0; j < tNum.length; j = j + 2) {
console.log("[" + tNum[j] + "," + tNum[j + 1] + "]");
console.log(tNum);
}

最后

以上就是无辜香烟为你收集整理的从一个数组中找出两个元素相加等于目标数字，时间复杂度为O(n)一、题目描述二、解题思路三、代码实现的全部内容，希望文章能够帮你解决从一个数组中找出两个元素相加等于目标数字，时间复杂度为O(n)一、题目描述二、解题思路三、代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。