我知道这是解决3Sum问题的蛮力和非最佳方法。它完成了检测总和为零的三元组的工作。但我正在寻找检测重复三胞胎的方法。我无法想出寻找已经考虑过的类似三元组合的逻辑。谢谢！
int** threeSum(int* nums, int numsSize, int *returnSize)
{
int count = 0;
int **res = NULL;
for (int i=0; i<(numsSize-2) ; i++)
{
for (int j=i+1; j<(numsSize-1) ; j++)
{
for(int k=j+1; k<numsSize ; k++)
{
if (0==(nums[i]+nums[j]+nums[k]))
{
if (count > 0)
{
res = (int **)realloc(res,sizeof(int *)*(count+1));
res[count] = (int *) malloc(sizeof(int)*3);
res[count][0] = nums[i];
res[count][1] = nums[j];
res[count][2] = nums[k];
count++;
}
else if (0==count)
{
res = (int **) malloc(sizeof(int *)*1);
res[0] = (int *) malloc(sizeof(int)*3);
res[0][0] = nums[i];
res[0][1] = nums[j];
res[0][2] = nums[k];
count++;
}
}
}
}
}
*returnSize=count;
if (count > 0)
return res;
else
return NULL;``
}
您可以简化代码，因为有冗余块：
realloc可以用NULL调用，就像malloc一样。res是count时，返回0是可以的，因为它被初始化为NULL。您可以检查重复项，您可以对三元组进行排序，并在插入之前在匹配列表中搜索它，也可以使用暴力：
int **threeSum(int *nums, int numsSize, int *returnSize) {
int count = 0;
int **res = NULL;
for (int i = 0; i < numsSize - 2; i++) {
for (int j = i + 1; j < numsSize - 1; j++) {
for (int k = j + 1; k < numsSize; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
int a = nums[i], b = nums[j], c = nums[k], n;
if (a > b) { int t = a; a = b; b = t; }
if (b > c) { int t = b; b = c; c = t; }
if (a > b) { int t = a; a = b; b = t; }
for (n = 0; n < count; n++) {
if (a == res[n][0] && b == res[n][1])
break;
}
if (n == count) {
int **p = realloc(res, sizeof(*p) * (count + 1));
int *p1 = malloc(sizeof(*p1) * 3);
if (p == NULL || p1 == NULL) {
for (n = 0; n < count; n++)
free(res[n]);
free(res);
free(p);
free(p1);
*returnSize = -1;
return NULL;
}
res = p;
p1[0] = a;
p1[1] = b;
p1[2] = c;
res[count] = p1;
count++;
}
break; // any other match would be a duplicate.
}
}
}
}
*returnSize = count;
return res;
}
笔记：
c == res[n][2]，因为res只包含匹配i和j测试更多元素。编辑我删除了这个不正确的答案，但现在启用它（虽然没有从各种评论更新，因为它仍然是错误的）。
为了它的价值，我将重复删除更改为：
int terms = 2;
// . . .
// remove duplicates
for(int i = 2; i < TERMS; i++) {
if(nums[i] != nums[terms - 1] || nums[i] != nums[terms - 2]) {
nums[terms++] = nums[i];
}
}
我没有创建一系列解决方案，只打印 - 我留给你。
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define TERMS 30 // length of array
#define MAXVAL 9 // value range + - MAXVAL
#define CHECK // compiler option quit when 0 sum is impossible
int cmp(const void *a, const void *b) {
return (*(int*)a) - (*(int*)b);
}
void show(char *legend, int *nums, int size)
{
printf("%s\n", legend);
for(int i = 0; i < size; i++) {
printf("%d ", nums[i]);
}
printf("\n\n");
}
int main(void) {
int nums[TERMS];
int terms = 1;
int sum;
int results = 0;
// build array
//srand((unsigned)time(NULL)); // comment out for repeatable values
for(int i = 0; i < TERMS; i++) {
nums[i] = rand() % (MAXVAL * 2 + 1) - MAXVAL;
}
show("input", nums, TERMS);
// sort array
qsort(nums, TERMS, sizeof nums[0], cmp);
show("sorted", nums, TERMS);
// remove duplicates
for(int i = 1; i < TERMS; i++) {
if(nums[i] != nums[terms - 1]) {
nums[terms++] = nums[i];
}
}
show("removed dups", nums, terms);
// find triplets with 0 sum
printf("zero sum triplets\n");
for(int i = 0; i < terms; i++) {
#ifdef CHECK
if(nums[i] > 0) {
// early termination if impossible
break;
}
#endif
for(int j = i + 1; j < terms; j++) {
for(int k = terms-1; k > j; k--) {
#ifdef CHECK
if(nums[k] < 0) {
// early termination if impossible
break;
}
#endif
sum = nums[i] + nums[j] + nums[k];
if(sum == 0) {
printf("%4d %4d %4d\n", nums[i], nums[j], nums[k]);
results++;
}
}
}
}
printf("\n%d results\n", results);
return 0;
}
程序输出
input -6 9 -2 5 8 2 -7 -6 -8 2 -4 -3 -3 3 -4 7 3 1 -8 -7 6 3 -2 -8 -2 4 8 -8 6 -7 sorted -8 -8 -8 -8 -7 -7 -7 -6 -6 -4 -4 -3 -3 -2 -2 -2 1 2 2 3 3 3 4 5 6 6 7 8 8 9 removed dups -8 -7 -6 -4 -3 -2 1 2 3 4 5 6 7 8 9 zero sum triplets -8 1 7 -8 2 6 -8 3 5 -7 -2 9 -7 1 6 -7 2 5 -7 3 4 -6 -3 9 -6 -2 8 -6 1 5 -6 2 4 -4 -3 7 -4 -2 6 -4 1 3 -3 -2 5 -3 1 2 16 results
既然你想坚持不懈，我就是在回应这个背景。您可以将检测到的三元组增加到3个整数的临时数组中，然后再将其存储在res中。检测到新的三元组时，对其进行排序并将其插入临时数组，将临时数组与存储在res数组中的数组进行比较，以检测重复集，如果重复则继续。
即。将res [0] [0]，res [0] [1]，res [0] [2]与temp [0]，temp [1]，temp [2]进行比较，并检测存在的每个三元组的重复项水库。并且由于每个res行都已排序，因此通过比较位置和位置应该很容易检测重复行。
让我们说几轮之后的res看起来如下：
-2 1 1
-3 1 2
-7 3 4
如果检测到一个新的三元组是[4,3，-7]，则在temp中它将是[-7,3,4]，当我们循环通过res并进行比较时，将检测到重复。
要对num [i]，num [j]，num [k]进行排序，您可以执行以下操作（再次保留在您的强力上下文中）：
if ((num[i] > num[j]))
{
/* Compare the first two numbers in num triplet */
temp[0] = num[j];
temp[1] = num[i];
}
else
{
temp[0] = num[i];
temp[1] = num[j];
}
//now compare the third number num[k]
if (num[k] < temp[0])
{
/* num[k] is the smallest number, shift the temp array to the right */
temp[2] = temp[1];
temp[1] = temp[0];
temp[0] = num[k]; /* Add the third number in the beginning of temp array */
}
else
if (num[k] >= temp[1])
{
/* num[k] is the shortest number, no shifting needed */
temp[2] = num[k]; /* Add the number num[k] to the end of temp array */
}
else
{
/* num[k] is in the middle, shift temp[1] to the right and insert num[k] */
temp[2] = temp [1]; /* Shift the last number in temp[k] */
temp[1] = num[k]; /* Overwrite temp[1] with the new number in num[k] which will put num[k] in the middle */
}
我还没有测试过这段代码。