如何优化“查找所有可能的三角形而不重复”代码

首先请注意，如果保证输入数组已排序，则在维护时i < j < m，您将永远不会得到（3,4,3）的组合。服用

    int a = nosniky[i];
    int b = nosniky[j];
    int c = nosniky[m];

将产生(a,b,c)不递减的顺序。因此，这根本不是问题。

但是，如果您的输入数据包含重复项，则可以得到重复项。例如，对于3,4,4,5您的输入，对于（i，j，m）=（0,1,3）和（i，j，m），您将得到相同的三元组（a，b，c）=（3,4,5） ）=（0,2,3）。

为避免这种情况，您只需要以一种聪明的方式增加i，j，m即可跳过重复项：if nosniky[1] == 4andnosniky[2] == 4您不应将其j从1增至2，而应一直增加它，直到发现nosniky[j]与nosniky[j-1]（或打到j == N）不同。

  int count = 0;

  .....  // sort nosniky[] in ascending order here
  
  for (int i = 0; i < N;) {
    int a = nosniky[i];

    for (int j = i + 1; j < N;) {
      int b = nosniky[j];

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (a + b > c && a + c > b && c + b > a) {
          int temp = jointInts(joinInts(a, b), c);

          trojuhelniky[count] = temp;
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }
      while (++j < N && nosniky[j] == b)
        ; // skip duplicates of the second edge
    }
    while (++i < N && nosniky[i] == a)
      ; // skip duplicates of the first edge
  }

  return count;

顺便说一句，一旦确保nosniky[]数组已排序，就知道c不小于aand b。然后，正如@pmg在评论中指出的那样，可以将三角形不等式的检验简化为第一个比较，因为肯定可以满足其余两个条件：

        if (a + b > c) {
          int temp = jointInts(joinInts(a, b), c);

          trojuhelniky[count] = temp;
          count ++;
        }

如果只计算三角形就可以了，不需要收集所有三角形，则可以简化最内层的循环：

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (a + b > c) {
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

遵循Michael Dorgan的评论建议，您可以通过提前终止c已知过大的长度来终止搜索，从而节省一些时间：

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)    // too large
          break;           // skip the rest

        if (a + b > c) {
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

然后，下一个条件变为重言式，因为它是对前一个条件的否定，因此我们可以摆脱它：

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)    // too large
          break;           // skip the rest

        count ++;

        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

如果期望的值非常大N，则还可以尝试优化c过小的值，例如使用二进制搜索。您将需要一个二进制搜索函数，该函数需要一个数组来搜索，一定范围的索引和一个目标值，并返回等于或大于目标（或范围的右端）的第一个值的索引（位置）未找到）。

      int c_minimal = b - a;

      // do binary search for c_minimal
      // between indices j+1 (inclusive) and N (exclusive)
      int initial_m = search(nosniky, j+1, N, c_minimal);

      // start from the first value big enough
      for (int m = initial_m; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)   // too large
          break;          // skip the rest

        count ++;

        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }