Zel*_*luX 155 arrays algorithm
给定一个整数数组,A 1,A 2,...,A n,包括负数和正数,以及另一个整数S.现在我们需要在数组中找到三个不同的整数,其总和最接近给定的整数S如果存在多个解决方案,则其中任何一个都可以.
您可以假设所有整数都在int32_t范围内,并且计算总和时不会发生算术溢出.S没什么特别的,只是随机挑选的数字.
有没有比强力搜索更有效的算法来找到三个整数？
Joh*_*lla 186
有没有比强力搜索更有效的算法来找到三个整数？
是的; 我们可以在O(n 2)时间内解决这个问题!首先,考虑一下你的问题P可以用一种略微不同的方式来表达,从而消除了对"目标值"的需求:
原来的问题
P:给定一个阵列A的n整数和目标值S,就存在着从一个3元组A求和以S？改性问题
P':给定一个阵列A的n整数,不存在从3元组A求和为零？
请注意,您可以从这个版本的问题,去P'从P通过从每个元素减去你的S/3 A,但现在你不需要目标值了.
显然,如果我们只是测试所有可能的3元组,我们就可以解决O(n 3)中的问题 - 这就是蛮力基线.有可能做得更好吗？如果我们以更聪明的方式选择元组怎么办？
首先,我们花费一些时间对数组进行排序,这使我们的初始惩罚为O(n log n).现在我们执行这个算法:
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.
}
该算法的工作原理是将三分,i,j,并k在不同的点在数组中.i从一开始就开始慢慢地运行到最后.k指向最后一个元素.j指向i已经开始的地方.我们迭代地尝试在各自的索引处对元素求和,并且每次发生以下情况之一:
j更接近最终选择未来最大数量.k接近开始选择下一个最小的数.对于每一个i,指针j和k将逐渐变得彼此靠近.最终它们会相互传递,此时我们不需要为此尝试任何其他因素i,因为我们只是以不同的顺序对相同的元素进行求和.在那之后,我们尝试下一个i并重复.
最终,我们将耗尽有用的可能性,或者我们将找到解决方案.你可以看到这是O(n 2),因为我们执行外循环O(n)次,我们执行内循环O(n)次.如果您真的很喜欢,可以通过将每个整数表示为位向量并执行快速傅立叶变换来实现这种子二次方,但这超出了本答案的范围.
注意:因为这是一个面试问题,我在这里做了一点作弊:这个算法允许多次选择相同的元素.也就是说,(-1,-1,2)将是一个有效的解决方案,因为(0,0,0).它也只能找到确切的答案,而不是最接近的答案,正如标题所提到的那样.作为对读者的练习,我将让你弄清楚如何使它只使用不同的元素(但这是一个非常简单的变化)和确切的答案(这也是一个简单的变化).
Cem*_*Cem 28
当然这是一个更好的解决方案,因为它更容易阅读,因此不容易出错.唯一的问题是,我们需要添加几行代码以避免多个选择一个元素.
另一个O(n ^ 2)解决方案(使用hashset).
// K is the sum that we are looking for
for i 1..n
int s1 = K - A[i]
for j 1..i
int s2 = s1 - A[j]
if (set.contains(s2))
print the numbers
set.add(A[i])
John Feminella的解决方案有一个错误.
在线
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
我们需要检查i,j,k是否都是不同的.否则,如果我的目标元素是6,如果我的输入数组包含{3,2,1,7,9,0,-4,6}.如果我打印出总和为6的元组,那么我也会得到0,0,6输出.为避免这种情况,我们需要以这种方式修改条件.
if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k])
这样的事情怎么样,这是O(n ^ 2)
for(each ele in the sorted array)
{
ele = arr[i] - YOUR_NUMBER;
let front be the pointer to the front of the array;
let rear be the pointer to the rear element of the array.;
// till front is not greater than rear.
while(front <= rear)
{
if(*front + *rear == ele)
{
print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
break;
}
else
{
// sum is > ele, so we need to decrease the sum by decrementing rear pointer.
if((*front + *rear) > ele)
decrement rear pointer.
// sum is < ele, so we need to increase the sum by incrementing the front pointer.
else
increment front pointer.
}
}
这会发现3个元素的总和是否与您的数字完全相等.如果你想要最接近,你可以修改它以记住最小的三角形(当前三元组的数量之间的差异),并在最后打印对应于最小三角形的三元组.
小智 5
请注意,我们有一个排序数组.该解决方案是类似于约翰的解决方案只知道它看起来的总和,并且不重复相同的元素.
#include <stdio.h>;
int checkForSum (int arr[], int len, int sum) { //arr is sorted
int i;
for (i = 0; i < len ; i++) {
int left = i + 1;
int right = len - 1;
while (right > left) {
printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]);
if (arr[right] + arr[left] + arr[i] - sum == 0) {
printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]);
return 1;
}
if (arr[right] + arr[left] + arr[i] - sum > 0)
right--;
else
left++;
}
}
return -1;
}
int main (int argc, char **argv) {
int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
int sum = 4;
printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum));
}