寻找独特的三胞胎

Question

在我的函数中，我必须从给定数组中找到给定数字 K 的所有唯一三元组。它找到了所有三胞胎，但其中许多三胞胎出现了两次或更多次，例如 1 1 5 与 1 5 1 或 5 1 1 等相同

有人可以帮我解决这个问题吗？

int triplet(int *array, int size, int K) {
  int i, j, k;
  int found = 0; /* triplets whose sum is equal to K */
  for(i = 0; i < size; i++) {
    for (j = 0; j < size; j++) {    
      for (k = 0; k < size; k++) {
        if(array[i] + array[j] + array[k] == K) {
          printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
          found++;
        }           
      }
    }
  }
  return found;
}

Answer 1

要排除组合，您可以尝试进行以下更改：

int triplet(int *array, int size, int K) {
  int i, j, k;
  int found = 0; /* triplets whose sum is equal to K */
  for(i = 0; i < size; i++) {
    for (j = i; j < size; j++) {    
      for (k = j; k < size; k++) {
        if(array[i] + array[j] + array[k] == K) {
          printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
          found++;
        }           
      }
    }
  }
  return found;
}

注意 for loop 声明中的 j = i 和 k = j 语句。通过这种方式，您将跳过您的案例可能的重复项，同时涵盖 i、j 和 k 变量的所有变体。

Answer 2

您不应该重复已经处理过的组合；一个可能的解决方案是从前一个 ID + 1 开始每个 for 循环，如下所示：

for(i = 0; i < size; i++) {
 for (j = i+1; j < size; j++) {    
  for (k = j+1; k < size; k++) {
    if(array[i] + array[j] + array[k] == K) {
      printf("Triplet Found : %d, %d, %d\n", array[i], array[j], array[k]);
      found++;
    }           
  }
}

设置j = i + 1;你防止同元素三胞胎！

寻找独特的三胞胎

Find unique triplets

arrays

function

triplet