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

下面是 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;
}

另一个提前检查并失败的解决方案是:

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

我在这里添加了一些单元测试: 给定数组返回 TrueIfThree 元素 SumZero 测试。

如果集合使用了太多的空间，我可以很容易地使用 java.util. BitSet，它将使用 O (n/w) 空间。

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

//创建一个 hashMap，键为 Integer，值为 ArrayList //使用 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 ]的和小于期望的和，那么有可能找到第三个数字，所以执行另一个 for 循环

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

//在这种情况下，我们现在寻找第三个值; 如果 Arr [ i ]和 arr [ j ]和 arr [ k ]是所需的和，然后将 arr [ i ]作为键，然后将 arr [ j ]和 arr [ k ]作为键的值添加到 ArrayList 中，从而将它们添加到 HashMap 中

          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 函数提取所有这些条目。效果很好。

这是 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. i.e. 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);
}
}

这可以在 O (n log (n))中有效地解决，如下所示。 我给出了一个解，它告诉我们任意三个数的和是否等于一个给定的数。

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,i.e. 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;
}
}

这个问题可以在 O (n ^ 2)中通过扩展2-和问题来解决，只需稍作修改。 A 是包含元素的向量，B 是所需的和。

Int 解: : three SumClosest (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;

获取这三个元素的程序。我刚刚排序的数组/列表第一，他们更新了基于每个三元组的 minCloseness。

public int[] threeSumClosest(ArrayList<Integer> A, int B) {
Collections.sort(A);
int ansSum = 0;
int ans[] = new int[3];
int minCloseness = Integer.MAX_VALUE;
for (int i = 0; i < A.size()-2; i++){
int j = i+1;
int k = A.size()-1;
while (j < k){
int sum = A.get(i) + A.get(j) + A.get(k);
if (sum < B){
j++;
}else{
k--;
}
if (minCloseness >  Math.abs(sum - B)){
minCloseness = Math.abs(sum - B);
ans[0] = A.get(i); ans[1] = A.get(j); ans[2] = A.get(k);
}
}
}
return ans;
}

下面是 Python 3代码

class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
result = set()
nums.sort()
L = len(nums)
for i in range(L):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1,L):
if j > i + 1 and nums[j] == nums[j-1]:
continue
l = j+1
r = L -1
while l <= r:
sum = nums[i] + nums[j] + nums[l]
result.add(sum)
l = l + 1
while l<=r and nums[l] == nums[l-1]:
l = l + 1
result = list(result)
min = result[0]
for i in range(1,len(result)):
if abs(target - result[i]) < abs(target - min):
min = result[i]
return min