参见英文答案 >
Finding three elements in an array whose sum is closest to a given number13个
我正试着在编码解决方案中节省时间.
我正试着在编码解决方案中节省时间.
我有一个名为tripletSum的函数,它接受两个参数x和a,其中x是数字,a是数组.
如果列表a包含三个加起来为x的元素,则该函数应返回true,否则返回false.
我创建了以下工作解决方案：
function tripletSum(x,a) {
for(var i = 0; i < a.length; i++) {
for(var j = i + 1; j < a.length; j++) {
for(var k = j + 1; k < a.length; k++) {
if((a[i] + a[j] + a[k]) === x) {
return true;
}
}
}
}
return false;
}
但这似乎不是最好的做法.目前运行此函数所需的时间是O(n ^ 3),如果我没有弄错,我认为可以改进O(n ^ 2)的时间复杂度.
无论如何,我可以改变这个代码来做到这一点？
编辑：这不是另一个问题的重复,因为我要求对我当前在JavaScript中的示例进行具体改进,这不是它在标记的重复问题中提出的要求.
解决方法
这是一个想法：首先需要对数组进行排序.之后,您可以有一个循环遍历从0到N-2(排他性)的所有元素.让我们称之为这个循环的索引.这就是数组排序的有用之处.我们将使用数组排序的知识来“挤压”“未处理的”子阵列(范围从i 1到第N个元素).您现在将左右两个值. left将指示未处理子数组的左索引,而right将指示数组未处理部分的正确索引.在开始时我们设置left = i 1和right = N – 1.我们计算总和a [i] a [left] a [right].现在我们有3个案例：
>如果sum = x则返回true
>如果总和> x然后我们需要降低总和,所以我们需要递减1(从右边挤压)
>如果总和< x然后我们需要使总和更大,所以我们需要向左递增1(从左边挤压)
以下是Javascript解决方案.
function tripletSum(x,a) {
a.sort(function(i,j) {
return i - j;
});
var N = a.length;
for(var i = 0; i < N - 2; i++) {
var left = i + 1,right = N - 1;
while(left < right) {
var sum = a[i] + a[left] + a[right];
if(sum === x) {
return true;
}
else if(sum > x) {
right--;
}
else {
left++;
}
}
}
return false;
}
时间复杂度为O(N ^ 2),并且没有使用额外的空间.