arrays - 寻找独特的三胞胎

Question

在我的函数中，我必须从给定数组中找到给定数字 K 的所有唯一三元组。它找到所有三元组，但其中许多存在两次或更多，就像or和 etc1 1 5一样。1 5 15 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;
}

注意声明中的j = iandk = j语句for loop。这样，您将跳过可能的重复案例，但涵盖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;你防止相同元素的三胞胎！