有多少种方法不能构成三角形？

Question

给定 n 和一组 n 个正整数，需要有多少种方法可以选择三个数字，使它们不能形成三角形。

示例：

3  
4 2 10

答案：

我的方法（在JAVA）

int[] arr = new int[n];//list of the numbers given
int count=0;//count of all such triplets
for(int i=0;i<n;i++)
    arr[i]=sc.nextInt();
Arrays.sort(arr);
for(int i=n-1;i>=0;i--)
{
    int j=0;
    int k= i-1;
     while(j<k && k>=0)
     {
         if(arr[i]>=arr[j]+arr[k])//condition for no triangle formation
          {
              count++;
              j++;//checking the next possible triplet by varying the third number
          }
          else if(arr[i]<arr[j]+arr[k])
          {
              j=0;
              k--;//now varying the second number if no such third number exists
          }
     }
}
System.out.println(count);

我的算法：

对列表进行排序后，我试图找到所有小于 arr[i] 的数字，使得 arr[i]>=arr[j]+arr[k]，在这种情况下三角形将不会形成。

但是我得到了这个解决方案的 timed-out。谁能建议更好的方法来解决这个问题？

Answer 1

适当的伪代码是：

SORT array //nlogn
INT counter = n*(n-1)*(n-2)/6;
FOR i = n - 1; i >= 2; i-- DO //largest length in a triangle - there must be two lower
    currentLargestNumber = array[i];
    FOR j = i - 1; j >= 1; j-- DO
        BINARY SEARCH FOR SMALLEST k for which array[k] + array[j] > array[i]
        counter -= j - k;
        IF nothingAddedInTheLastIteration DO
            BREAK;
        END_IF
    END_FOR
    IF nothingAddedInTheLastIteration DO
        BREAK;
    END_IF
END_FOR

我假设不会有超过 3 个相同值的输入。如果有这种可能性，请删除不必要的值。

在每个循环中，您应该检查是否添加了任何三角形。如果没有，打破这个循环。

Answer 2

这个问题可以用双指针技术来解决，但是我们不会计算有多少个三元组不能组成一个三角形，我们会寻找相反的结果，最后减去结果来自 C(n,3) = (n)(n-1)(n-2)/6。让我们对数组 arr、arr[0] < arr[1] .. < arr[n-1] 进行排序。对于给定的一对 i < j，找到索引 k > j、s.t。 arr[i] + arr[j] <= arr[k] 和 arr[i] + arr[j] > arr[k-1]。这将导致额外的 k - j -1 三元组（三元组是：{i,j,j+1},{i,j,j+2},..,{i,j,k-1}。现在请注意，每当我们增加 j 时，我们不需要重置 k 的值，这有助于保持总时间复杂度 O(n^2)。

//arr is already sorted
long triangles = 0;
for(int i = 0; i < n-2; i++){
   int k = i + 2;
   for(int j = i + 1; j < n; j++){
      while(arr[i] + arr[j] > arr[k] && k < n){
         k++;
      }
      triangles += k-j-1;
   }
} 
long answer = n*(n-1)*(n-2)/6 - triangles;

有多少种方法不能构成三角形？

Number of ways one cannot make a triangle?

java

algorithm

performance

time

time-limiting