查找数组中的三个元素，其总和最接近给定的数字

给定一个整数数组A ₁ ，A ₂ ，…，A _n ，包括负数和正数，以及另一个整数S.现在我们需要在数组中find三个不同的整数，其总和最接近给定的整数S如果存在多个解决scheme，其中任何一个都可以。

你可以假设所有的整数都在int32_t范围内，并且在计算总和时不会发生算术溢出。 S没什么特别之处，只是一个随机挑选的数字

除蛮力search外，是否还有其他有效的algorithm来找出这三个整数？

Answer 1

除蛮力search外，是否还有其他有效的algorithm来找出这三个整数？

是的; 我们可以在O（n ² ）时间内解决这个问题！ 首先，考虑一下，你的问题P可以用一个稍微不同的方式等价地表示：消除“目标价值”的需要：

原始问题P ：给定一个n整数的数组A和一个目标值S ，是否存在一个从A到A的三元组？

修改后的问题P' ：给定一个n整数的数组A ，是否存在一个从A到A的三元组？

注意，你可以从P'这个版本的P'减去你的S / 3从A每个元素，但现在你不需要目标值了。

显然，如果我们简单地testing所有可能的三元组，我们就可以解决O（n ³ ）中的问题 – 这就是蛮力基线。 有没有可能做得更好？ 如果我们以更聪明的方式select元组呢？

首先，我们花费一些时间对数组进行sorting，这使得我们的初始惩罚为O（n log n）。 现在我们执行这个algorithm：

 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. } 

该algorithm通过在数组中的不同点上放置三个指针i ， j和k工作。 i从i开始就开始慢慢地走到最后。 k指向最后一个元素。 j指向i开始的地方。 我们反复尝试在各自的索引处对元素进行求和，并且每次发生以下情况之一时：

• 总和是完全正确的！ 我们find了答案。
• 总和太小了。 将j移近末尾以select下一个最大号码。
• 总和太大了。 将k靠近开头，select下一个最小的数字。

对于每个i ， j和k的指针将逐渐接近彼此。 最终他们会相互传递，在这一点上，我们不需要为我做任何其他的事情，因为我们会按照不同的顺序总结相同的元素。 在那之后，我们尝试接下来的i并重复。

最终，我们要么耗尽有用的可能性，要么find解决scheme。 你可以看到这是O（n ² ），因为我们执行外部循环O（n）次并执行内部循环O（n）次。 通过将每个整数表示为位vector并执行快速傅立叶变换，可以实现这种次级方式，如果你真的很喜欢，但这超出了这个答案的范围。

---

注意：因为这是一个面试问题，所以我在这里作了一点点的说明：这个algorithm允许多次select相同的元素。 也就是说，（-1，-1，2）将是一个有效的解决scheme，就像（0，0，0）一样。 它也只能find确切的答案，而不是最接近的答案，因为标题提到。 作为读者的一个练习，我会让你弄清楚如何使它与独特的元素（但它是一个非常简单的变化）和确切的答案（这也是一个简单的改变）的工作。

Answer 2

当然这是一个更好的解决scheme，因为它更容易阅读，因此不易出错。 唯一的问题是，我们需要添加几行代码来避免多个元素的select。

另一个O（n ^ 2）解决scheme（通过使用一个哈希集）。

 // 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]) 

Answer 3

我相信我们可以修改@John Feminella使用二进制search的优秀答案，从而将运行时间减less到O（nlgn）。 自定义函数binary_search（alist，value，low，high）返回值的索引，否则返回-10，如果它在左边终止，则返回-20;如果终止在右边，则返回-20：

 def triplet_sum(alist, total): alist.sort() #modifies the list in place - more efficient than sorted() but not great if we need the list unmodified left, right = 0, len(alist) - 1 while right > left: elem = total - alist[left] - alist[right] mid = binary_search(alist, elem, left, right) if mid >= 0: #found return (alist[left], alist[mid], alist[right]) elif mid == -10: #terminated left right -= 1 elif mid == -20: #terminated right left += 1 return None 

• 首先sorting列表 – O（nlgn）时间
• 左开始为0，右为n-1（最后一个索引）
• 二进制search完成总和 – O（logn）时间的第三个元素
• 如果find，则返回三元组
• 如果二分查找终止在列表的左侧，则向右递减
• 如果二进制search在右侧终止，则向左递增

while循环运行O（n）次，每次执行O（logn）工作，总共为O（nlogn）。 让我知道这是否有帮助，我很乐意听到任何改进/build议。

Answer 4

那么这样的事情呢，是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个元素的总和恰好等于你的数字。 如果你想要最接近的，你可以修改它以记住最小的三angular洲（当前三重数量之间的差异），并在最后打印三angular形对应于最小的三angular洲。

Answer 5

John Feminella的解决scheme有一个错误。

在线

 if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) 

我们需要检查i，j，k是否完全不同。 否则，如果我的目标元素是6 ，如果我的input数组包含{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]) 

Answer 6

请注意，我们有一个sorting的数组。 这个解决scheme类似于约翰的解决scheme，只是它寻找的总和，并不重复相同的元素。

 #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)); } 

Answer 7

这里是C ++代码：

 bool FindSumZero(int a[], int n, int& x, int& y, int& z) { if (n < 3) return false; sort(a, a+n); for (int i = 0; i < n-2; ++i) { int j = i+1; int k = n-1; while (k >= j) { int s = a[i]+a[j]+a[k]; if (s == 0 && i != j && j != k && k != i) { x = a[i], y = a[j], z = a[k]; return true; } if (s > 0) --k; else ++j; } } return false; } 

Answer 8

非常简单的N ^ 2 * logN解决scheme：对input数组进行sorting，然后遍历所有对A _i ，A _j （N ^ 2次），并且为每一对检查是否（S – A _i – A _j ） logN时间）。

另一个O（S * N）解决scheme使用经典的dynamic规划方法。

简而言之：

创build一个二维数组V [4] [S + 1]。 填写这样一个方式，即：

V [0] [0] = 1，V [0] [x] = 0;

对于任何i，V 1 [A _i ] = 1，对于所有其他x，V 1 [x] = 0

V [2] [A _i + A _j ] = 1，对于任何i，j。 对于所有其他x，V [2] [x] = 0

V [3] [任意3个元素的和] = 1。

为了填充它，遍历A _i ，对于每一个_我从右到左遍历数组。

Answer 9

在上面的Johnalgorithm中存在一个问题，即使它试图find确切的答案。 当从A []中减去S / 3时，有可能引入错误的答案：

input：[2,3，-1,1]，目标= 5正确的输出：[2,3，-1]或[2,3,1]，差值为1。

基于上面的Johnalgorithm，它如下所示：从A []中减去S / 3 = 1：

  A'[] = [1, 2, -2, 0]. 

如果selectoutput = [2，-2，0]，那么我们就有了精确的匹配。 在原始的A []中检索这些元素的索引，我们得到输出元素= [3，-1,1]，这是错误的。

Answer 10

这可以在O（n log（n））中有效地解决，如下所示。 我给解决scheme，告诉如果任何三个数字的总和等于一个给定的数字。

 import java.util.*; public class MainClass { public static void main(String[] args) { int[] a = {-1, 0, 1, 2, 3, 5, -4, 6}; System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString()); } public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) { //O(n log (n)) Arrays.sort(array); System.out.println(Arrays.toString(array)); int leftIndex = 0; int rightIndex = array.length - 1; //O(n) while (leftIndex + 1 < rightIndex - 1) { //take sum of two corners int sum = array[leftIndex] + array[rightIndex]; //find if the number matches exactly. Or get the closest match. //here i am not storing closest matches. You can do it for yourself. //O(log (n)) complexity int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array); //if exact match is found, we already got the answer if (-1 == binarySearchClosestIndex) { System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum))); return true; } //if exact match is not found, we have to decide which pointer, left or right to move inwards //we are here means , either we are on left end or on right end else { //we ended up searching towards start of array,ie we need a lesser sum , lets move inwards from right //we need to have a lower sum, lets decrease right index if (binarySearchClosestIndex == leftIndex + 1) { rightIndex--; } else if (binarySearchClosestIndex == rightIndex - 1) { //we need to have a higher sum, lets decrease right index leftIndex++; } } } return false; } public static int binarySearch(int start, int end, int elem, int[] array) { int mid = 0; while (start <= end) { mid = (start + end) >>> 1; if (elem < array[mid]) { end = mid - 1; } else if (elem > array[mid]) { start = mid + 1; } else { //exact match case //Suits more for this particular case to return -1 return -1; } } return mid; } } 

Answer 11

减less：我认为@John Feminella解决schemeO（N2）是最优雅的。 我们仍然可以减lesssearch元组的A [n]。 通过观察A [k]使得所有元素都在A [0] – A [k]中，当我们的search数组很大，SUM（s）非常小时。

A [0]最小： – 升序sorting数组。

s = 2A [0] + A [k]：给定s和A []我们可以在log（n）时间使用二分searchfindA [k]。

Answer 12

另一种早期检查失败的解决scheme：

 public boolean solution(int[] input) { int length = input.length; if (length < 3) { return false; } // x + y + z = 0 => -z = x + y final Set<Integer> z = new HashSet<>(length); int zeroCounter = 0, sum; // if they're more than 3 zeros we're done for (int element : input) { if (element < 0) { z.add(element); } if (element == 0) { ++zeroCounter; if (zeroCounter >= 3) { return true; } } } if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) { return false; } else { for (int x = 0; x < length; ++x) { for (int y = x + 1; y < length; ++y) { sum = input[x] + input[y]; // will use it as inverse addition if (sum < 0) { continue; } if (z.contains(sum * -1)) { return true; } } } } return false; } 

我在这里添加了一些unit testing： GivenArrayReturnTrueIfThreeElementsSumZeroTest 。

如果这个集合使用太多的空间，我可以很容易地使用一个java.util.BitSet来使用O（n / w） 空间 。

Answer 13

这里是在Java程序是O（N ^ 2）

 import java.util.Stack; public class GetTripletPair { /** Set a value for target sum */ public static final int TARGET_SUM = 32; private Stack<Integer> stack = new Stack<Integer>(); /** Store the sum of current elements stored in stack */ private int sumInStack = 0; private int count =0 ; public void populateSubset(int[] data, int fromIndex, int endIndex) { /* * Check if sum of elements stored in Stack is equal to the expected * target sum. * * If so, call print method to print the candidate satisfied result. */ if (sumInStack == TARGET_SUM) { print(stack); } for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) { if (sumInStack + data[currentIndex] <= TARGET_SUM) { ++count; stack.push(data[currentIndex]); sumInStack += data[currentIndex]; /* * Make the currentIndex +1, and then use recursion to proceed * further. */ populateSubset(data, currentIndex + 1, endIndex); --count; sumInStack -= (Integer) stack.pop(); }else{ return; } } } /** * Print satisfied result. ie 15 = 4+6+5 */ private void print(Stack<Integer> stack) { StringBuilder sb = new StringBuilder(); sb.append(TARGET_SUM).append(" = "); for (Integer i : stack) { sb.append(i).append("+"); } System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); } private static final int[] DATA = {4,13,14,15,17}; public static void main(String[] args) { GetAllSubsetByStack get = new GetAllSubsetByStack(); get.populateSubset(DATA, 0, DATA.length); } } 

Answer 14

这个问题可以在O（n ^ 2）中通过稍微修改来扩展2-sum问题来解决.A是包含元素的向量，B是所需的总和。

int Solution :: threeSumClosest（vector＆A，int B）{

 sort(A.begin(),A.end()); int k=0,i,j,closest,val;int diff=INT_MAX; while(k<A.size()-2) { i=k+1; j=A.size()-1; while(i<j) { val=A[i]+A[j]+A[k]; if(val==B) return B; if(abs(B-val)<diff) { diff=abs(B-val); closest=val; } if(B>val) ++i; if(B<val) --j; } ++k; } return closest; 

Answer 15

我在n ^ 3中做了这个，我的伪代码在下面;

//创build一个key为Integer，值为ArrayList的hashMap //使用for循环遍历list，list中的每个值都会从下一个值开始迭代;

 for (int i=0; i<=arr.length-1 ; i++){ for (int j=i+1; j<=arr.length-1;j++){ 

//如果arr [i]和arr [j]的总和小于所需的总和，那么就有可能find第三个数字，所以另一个for循环

  if (arr[i]+arr[j] < sum){ for (int k= j+1; k<=arr.length-1;k++) 

//在这种情况下，我们正在寻找第三个值; 如果arr [i]和arr [j]和arr [k]的总和是所需的总和，则将这些值加到HashMap中，将arr [i]作为关键字，然后将arr [j]和arr [k] ArrayList中的那个键的值

  if (arr[i]+arr[j]+arr[k] == sum){ map.put(arr[i],new ArrayList<Integer>()); map.get(arr[i]).add(arr[j]); map.get(arr[i]).add(arr[k]);} 

在此之后，你现在有一个字典，所有的条目代表三个值添加到所需的总和。 使用HashMap函数提取所有这些条目。 这工作完美。

Answer 16

 #include<stdio.h> #include<math.h> int main() { int a[7],high=6,low=0,sum=0,k,i,j,c; printf("\nEnter 5 numbers : "); for(i=0; i<7; i++) { scanf("%d",&a[i]); } printf("\nEnter c :"); scanf("%d",&c); for(i=0;i<5;i++) { for(j=i+2;j<7;j++) { if(c-(a[i]+a[i+1])==a[j]) { printf(" %d ",a[i]); printf("%d",a[i+1]); printf(" %d ",a[j]); printf("\n\n%d %d %d are the required numbers",a[i],a[i+1],a[j]); exit(0); } } } }