查找给定整数的不同三元组总和的数量

Question

你得到了一个随机整数数组/列表(ARR)和一个数字X.查找并返回数组/列表中总和为X的不同三元组的数量。

我写了这段代码：

public class Solution { 
public static void merge(int arr[], int lb, int mid, int ub) {
int n1 = mid - lb + 1;
int n2 = ub - mid;

int arr1[] = new int[n1];
int arr2[] = new int[n2];

for (int i = 0; i < n1; i++)
arr1[i] = arr[lb + i];
for (int j = 0; j < n2; j++)
arr2[j] = arr[mid + 1 + j];

int i = 0, j = 0;

int k = lb;
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j])
arr[k] = arr1[i++];
else
arr[k] = arr2[j++];
k++;
}

while (i < n1)
arr[k++] = arr1[i++];

while (j < n2)
arr[k++] = arr2[j++];
}

public static void mergeSort(int arr[], int lb, int ub) {
if (lb < ub) {
int mid = lb + (ub - lb) / 2;

mergeSort(arr, lb, mid);
mergeSort(arr, mid + 1, ub);
merge(arr, lb, mid, ub);
}
}
public static int tripletSum(int[] arr, int num) {
mergeSort(arr, 0, arr.length - 1); 
int n = arr.length;
int count = 0;

for (int i = 0; i < n - 2; i++) {
int sum = num - arr[i];

int j = i + 1;
int k = n - 1;
while (j < k) {
if (arr[j] + arr[k] == sum) {
count++;
k--;
} else if (arr[j] + arr[k] > sum) {
k--;
} else
j++;
}
}
return count;
}
}

输入数组为 -1 3 3 3 3 3 3

输入数字 =9

生成的输出 -10

预期产出 -20

帮我解决这个问题，我正在尝试找到解决方案很多小时。此外，程序的时间复杂度不应超过 O(n²)。

Answer 1

给定的代码适用于所有测试用例。

import java.util.Arrays;
public class Solution {
public static int tripletSum(int[] arr, int num) {
Arrays.sort(arr);
int n = arr.length;

int Numtripletsum = 0;
for(int i=0;i<n;i++)
{
int pairSumFor = num - arr[i];
int numPairs = pairSum(arr, (i+1), (n-1), pairSumFor);
Numtripletsum+=numPairs;
}
return Numtripletsum;

}
private static int pairSum(int[] arr, int startIndex, int endIndex, int num ){

int numPair = 0;
while(startIndex < endIndex){
if(arr[startIndex] + arr[endIndex] < num){
startIndex++;
}
else if(arr[startIndex] + arr[endIndex] > num){
endIndex--;
}
else
{
int elementAtStart = arr[startIndex];
int elementAtEnd = arr[endIndex];

if(elementAtStart == elementAtEnd){
int totalElementsFromStartToEnd = (endIndex - startIndex) + 1;
numPair += (totalElementsFromStartToEnd * (totalElementsFromStartToEnd -1) /2);

return numPair;
}
int tempStartIndex = startIndex + 1;
int tempEndIndex = endIndex - 1;

while(tempStartIndex <= tempEndIndex && arr[tempStartIndex] == elementAtStart){
tempStartIndex+=1;
}
while(tempEndIndex >= tempStartIndex && arr[tempEndIndex] == elementAtEnd){
tempEndIndex-=1;
}
int totalElementsFromStart = (tempStartIndex - startIndex);
int totalElementsFromEnd = (endIndex - tempEndIndex);

numPair += (totalElementsFromStart * totalElementsFromEnd);

startIndex = tempStartIndex;
endIndex = tempEndIndex;
}
}
return numPair;
}
}

Answer 2

我是这样做的，希望我能很好地理解它。

public static int tripletSum(int[] arr, int num) {
int loops = 0; // just to check the quality of the code
int counter = 0;
for (int i1 = 0; i1 < arr.length - 2; i1++) {
for (int i2 = i1 + 1; i2 < arr.length - 1; i2++) {
for (int i3 = i2 + 1; i3 < arr.length; i3++) {
loops++;
if (arr[i1] + arr[i2] + arr[i3] == num) {
counter++;
}
}
}
}
// Check for not exceeding O(n^2)
if (loops <= arr.length * arr.length) {
System.io.println("Well done");
} else {
System.io.println("Too many cycles");
}
return counter;
}

我在阵列上从"左"到"右"迭代，并越来越多地向"右"走。

1st, 2nd, 3rd
1st, 2nd, 4th
...
1st, 2nd, nth
2nd, 3rd, 4th
2nd, 3rd, 5th
...
2nd, 3rd, nth
.
.
.
nth - 2, nth - 1, nth

我迭代了 35 次，但可以迭代 7^2 = 49 次 -->"干得好">

Answer 3

你错过了一个循环。固定代码：

public static int tripletSum(int[] arr, int num) {
//Your code goes here
mergeSort(arr, 0, arr.length - 1);
int n = arr.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
int sum = num - arr[i];

for (int j = i+1; j < n-1; j++) {
int k = n-1;
while (j < k) {
if (arr[j] + arr[k] == sum) {
count++;
k--;
} else if (arr[j] + arr[k] > sum) {
k--;
} else {
j++;
}
}
}
}
return count;
}

Answer 4

好的，然后是优化版本：

public static int tripletSum(int[] arr, int num) {
//Your code goes here
mergeSort(arr, 0, arr.length - 1);
int n = arr.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
int sum = num - arr[i];
int maxK = n - 1;
for (int j = i + 1; j < n - 1; j++) {
int k = maxK;
while (j < k) {
if (arr[j] + arr[k] == sum) {
count++;
k--;
} else if (arr[j] + arr[k] > sum) {
k--;
maxK--;
} else {
j++;
}
}
}
}
return count;
}