给定一个未排序的正整数数组，求三个不同数组元素作为三角形的三条边可以形成的三角形数。如果一个三角形可以由三个值组成，则两个值（或边）之和必须大于第三个值（或边）。 例如：
null
Input: arr= {4, 6, 3, 7}Output: 3Explanation: There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle. Input: arr= {10, 21, 22, 100, 101, 200, 300}.Output: 6Explanation: There can be 6 possible triangles:{10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}
方法1（暴力）
- 方法： 蛮力方法是运行三个循环，并跟踪到目前为止可能出现的三角形数量。三个循环从一个数组中选择三个不同的值。最里面的循环检查三角形属性，该属性指定任意两条边的和必须大于第三条边的值）。
- 算法：
- 从上一个循环的索引到数组的结尾，每个循环运行三个嵌套循环，即从0到n运行第一个循环，从i到n运行j，从j到n运行k。
- 首先对数组进行排序。检查数组[i]+array[j]>array[k]，即两边之和是否大于第三个
- 如果三个条件都匹配，则增加计数。
- 打印计数
- 实施：
C++
// C++ code to count the number of // possible triangles using brute // force approach #include <bits/stdc++.h> using namespace std; // Function to count all possible // triangles with arr[] elements int findNumberOfTriangles( int arr[], int n) { // Count of triangles int count = 0; // The three loops select three // different values from array for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // The innermost loop checks for // the triangle property for ( int k = j + 1; k < n; k++) // Sum of two sides is greater // than the third if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i]) count++; } } return count; } // Driver code int main() { int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; int size = sizeof (arr) / sizeof (arr[0]); cout << "Total number of triangles possible is " << findNumberOfTriangles(arr, size); return 0; } |
JAVA
// Java code to count the number of // possible triangles using brute // force approach import java.io.*; import java.util.*; class GFG { // Function to count all possible // triangles with arr[] elements static int findNumberOfTriangles( int arr[], int n) { // Sort the array Arrays.sort(arr); // Count of triangles int count = 0 ; // The three loops select three // different values from array for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // The innermost loop checks for // the triangle property for ( int k = j + 1 ; k < n; k++) // Sum of two sides is greater // than the third if (arr[i] + arr[j] > arr[k]) { count++; } } } return count; } // Driver code public static void main(String[] args) { int arr[] = { 10 , 21 , 22 , 100 , 101 , 200 , 300 }; int size = arr.length; System.out.println( "Total number of triangles possible is " + findNumberOfTriangles(arr, size)); } } // This code is contributed by shubhamsingh10 // Updated by rajatsangrame |
Python3
# Python3 code to count the number of # possible triangles using brute # force approach # Function to count all possible # triangles with arr[] elements def findNumberOfTriangles(arr, n): # Count of triangles count = 0 # The three loops select three # different values from array for i in range (n): for j in range (i + 1 , n): # The innermost loop checks for # the triangle property for k in range (j + 1 , n): # Sum of two sides is greater # than the third if (arr[i] + arr[j] > arr[k] and arr[i] + arr[k] > arr[j] and arr[k] + arr[j] > arr[i]): count + = 1 return count # Driver code arr = [ 10 , 21 , 22 , 100 , 101 , 200 , 300 ] size = len (arr) print ( "Total number of triangles possible is" , findNumberOfTriangles(arr, size)) # This code is contributed by shubhamsingh10 |
C#
// C# code to count the number of // possible triangles using brute // force approach using System; class GFG{ // Function to count all possible // triangles with arr[] elements static int findNumberOfTriangles( int [] arr, int n) { // Count of triangles int count = 0; // The three loops select three // different values from array for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // The innermost loop checks for // the triangle property for ( int k = j + 1; k < n; k++) // Sum of two sides is greater // than the third if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i]) count++; } } return count; } // Driver code static public void Main () { int [] arr = { 10, 21, 22, 100, 101, 200, 300 }; int size = arr.Length; Console.WriteLine( "Total number of triangles possible is " +findNumberOfTriangles(arr, size)); } } // This code is contributed by shubhamsingh10 |
Javascript
<script> // Javascript program for the above approach // Function to count all possible // triangles with arr[] elements function findNumberOfTriangles(arr, n) { // Count of triangles let count = 0; // The three loops select three // different values from array for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // The innermost loop checks for // the triangle property for (let k = j + 1; k < n; k++) // Sum of two sides is greater // than the third if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i]) count++; } } return count; } // Driver Code let arr = [ 10, 21, 22, 100, 101, 200, 300 ]; let size = arr.length; document.write( "Total number of triangles possible is " + findNumberOfTriangles(arr, size)); // This code is contributed by souravghosh0416. </script> |
输出：
Total number of triangles possible is 6
- 复杂性分析：
- 时间复杂性： O（N^3），其中N是输入数组的大小。
- 空间复杂性： O（1）
方法2 : 这是一种复杂而有效的方法，可以减少 O（n^3） 到 O（n^2） 三角形的两条边是固定的，可以用这两条边来计算。
- 方法： 首先按升序对数组进行排序。然后使用两个循环。外环固定第一条边，内环固定第二条边，然后找到第三条边的最远索引（大于两侧索引），其长度小于其他两条边的总和。因此，可以找到一系列第三方的值，其中可以保证其长度大于其他单独的边，但小于两个边的总和。
- 算法： 设a、b和c为三面。三角形必须满足以下条件（两条边之和大于第三条边） i） a+b>c ii）b+c>a iii）a+c>b 下面是计算三角形的步骤。
- 按升序对数组排序。
- 现在运行嵌套循环。外循环从头到尾运行，内循环从头到尾运行 索引+1 从第一圈一直到最后。以第一个循环的循环计数器为例 我 第二个循环是 J .再来一个变量 k=i+2
- 现在有两个要点 我 和 J 哪里 数组[i] 和 数组[j] 表示三角形的两侧。固定时间 我 和 J ，求出满足三角形条件的第三条边的个数。i、 e.找出最大的价值 数组[k] 以至于 数组[i] + 数组[j] > 数组[k]
- 所以当我们得到最大值时，第三方的计数是 k-j ，将其添加到总计数中。
- 现在总结所有有效的数据对 我 和 J 哪里 i
- 实施：
C++
// C++ program to count number of triangles that can be // formed from given array #include <bits/stdc++.h> using namespace std; /* Following function is needed for library function qsort(). Refer http:// www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ int comp( const void * a, const void * b) { return *( int *)a > *( int *)b; } // Function to count all possible triangles with arr[] // elements int findNumberOfTriangles( int arr[], int n) { // Sort the array elements in non-decreasing order qsort (arr, n, sizeof (arr[0]), comp); // Initialize count of triangles int count = 0; // Fix the first element. We need to run till n-3 // as the other two elements are selected from // arr[i+1...n-1] for ( int i = 0; i < n - 2; ++i) { // Initialize index of the rightmost third // element int k = i + 2; // Fix the second element for ( int j = i + 1; j < n; ++j) { // Find the rightmost element which is // smaller than the sum of two fixed elements // The important thing to note here is, we // use the previous value of k. If value of // arr[i] + arr[j-1] was greater than arr[k], // then arr[i] + arr[j] must be greater than k, // because the array is sorted. while (k < n && arr[i] + arr[j] > arr[k]) ++k; // Total number of possible triangles that can // be formed with the two fixed elements is // k - j - 1. The two fixed elements are arr[i] // and arr[j]. All elements between arr[j+1]/ to // arr[k-1] can form a triangle with arr[i] and arr[j]. // One is subtracted from k because k is incremented // one extra in above while loop. // k will always be greater than j. If j becomes equal // to k, then above loop will increment k, because arr[k] // + arr[i] is always greater than arr[k] if (k > j) count += k - j - 1; } } return count; } // Driver code int main() { int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; int size = sizeof (arr) / sizeof (arr[0]); cout << "Total number of triangles possible is " << findNumberOfTriangles(arr, size); return 0; } // This code is contributed by rathbhupendra |
C
// C program to count number of triangles that can be // formed from given array #include <stdio.h> #include <stdlib.h> /* Following function is needed for library function qsort(). Refer http:// www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ int comp( const void * a, const void * b) { return *( int *)a > *( int *)b; } // Function to count all possible triangles with arr[] // elements int findNumberOfTriangles( int arr[], int n) { // Sort the array elements in non-decreasing order qsort (arr, n, sizeof (arr[0]), comp); // Initialize count of triangles int count = 0; // Fix the first element. We need to run till n-3 // as the other two elements are selected from // arr[i+1...n-1] for ( int i = 0; i < n - 2; ++i) { // Initialize index of the rightmost third // element int k = i + 2; // Fix the second element for ( int j = i + 1; j < n; ++j) { // Find the rightmost element which is // smaller than the sum of two fixed elements // The important thing to note here is, we // use the previous value of k. If value of // arr[i] + arr[j-1] was greater than arr[k], // then arr[i] + arr[j] must be greater than k, // because the array is sorted. while (k < n && arr[i] + arr[j] > arr[k]) ++k; // Total number of possible triangles that can // be formed with the two fixed elements is // k - j - 1. The two fixed elements are arr[i] // and arr[j]. All elements between arr[j+1]/ to // arr[k-1] can form a triangle with arr[i] and arr[j]. // One is subtracted from k because k is incremented // one extra in above while loop. // k will always be greater than j. If j becomes equal // to k, then above loop will increment k, because arr[k] // + arr[i] is always greater than arr[k] if (k > j) count += k - j - 1; } } return count; } // Driver program to test above functionarr[j+1] int main() { int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; int size = sizeof (arr) / sizeof (arr[0]); printf ( "Total number of triangles possible is %d " , findNumberOfTriangles(arr, size)); return 0; } |
JAVA
// Java program to count number of triangles that can be // formed from given array import java.io.*; import java.util.*; class CountTriangles { // Function to count all possible triangles with arr[] // elements static int findNumberOfTriangles( int arr[]) { int n = arr.length; // Sort the array elements in non-decreasing order Arrays.sort(arr); // Initialize count of triangles int count = 0 ; // Fix the first element. We need to run till n-3 as // the other two elements are selected from arr[i+1...n-1] for ( int i = 0 ; i < n - 2 ; ++i) { // Initialize index of the rightmost third element int k = i + 2 ; // Fix the second element for ( int j = i + 1 ; j < n; ++j) { /* Find the rightmost element which is smaller than the sum of two fixed elements The important thing to note here is, we use the previous value of k. If value of arr[i] + arr[j-1] was greater than arr[k], then arr[i] + arr[j] must be greater than k, because the array is sorted. */ while (k < n && arr[i] + arr[j] > arr[k]) ++k; /* Total number of possible triangles that can be formed with the two fixed elements is k - j - 1. The two fixed elements are arr[i] and arr[j]. All elements between arr[j+1] to arr[k-1] can form a triangle with arr[i] and arr[j]. One is subtracted from k because k is incremented one extra in above while loop. k will always be greater than j. If j becomes equal to k, then above loop will increment k, because arr[k] + arr[i] is always/ greater than arr[k] */ if (k > j) count += k - j - 1 ; } } return count; } public static void main(String[] args) { int arr[] = { 10 , 21 , 22 , 100 , 101 , 200 , 300 }; System.out.println( "Total number of triangles is " + findNumberOfTriangles(arr)); } } /*This code is contributed by Devesh Agrawal*/ |
Python3
# Python function to count all possible triangles with arr[] # elements def findnumberofTriangles(arr): # Sort array and initialize count as 0 n = len (arr) arr.sort() count = 0 # Fix the first element. We need to run till n-3 as # the other two elements are selected from arr[i + 1...n-1] for i in range ( 0 , n - 2 ): # Initialize index of the rightmost third element k = i + 2 # Fix the second element for j in range (i + 1 , n): # Find the rightmost element which is smaller # than the sum of two fixed elements # The important thing to note here is, we use # the previous value of k. If value of arr[i] + # arr[j-1] was greater than arr[k], then arr[i] + # arr[j] must be greater than k, because the array # is sorted. while (k < n and arr[i] + arr[j] > arr[k]): k + = 1 # Total number of possible triangles that can be # formed with the two fixed elements is k - j - 1. # The two fixed elements are arr[i] and arr[j]. All # elements between arr[j + 1] to arr[k-1] can form a # triangle with arr[i] and arr[j]. One is subtracted # from k because k is incremented one extra in above # while loop. k will always be greater than j. If j # becomes equal to k, then above loop will increment k, # because arr[k] + arr[i] is always greater than arr[k] if (k>j): count + = k - j - 1 return count # Driver function to test above function arr = [ 10 , 21 , 22 , 100 , 101 , 200 , 300 ] print ( "Number of Triangles:" , findnumberofTriangles(arr)) # This code is contributed by Devesh Agrawal |
C#
// C# program to count number // of triangles that can be // formed from given array using System; class GFG { // Function to count all // possible triangles // with arr[] elements static int findNumberOfTriangles( int [] arr) { int n = arr.Length; // Sort the array elements // in non-decreasing order Array.Sort(arr); // Initialize count // of triangles int count = 0; // Fix the first element. We // need to run till n-3 as // the other two elements are // selected from arr[i+1...n-1] for ( int i = 0; i < n - 2; ++i) { // Initialize index of the // rightmost third element int k = i + 2; // Fix the second element for ( int j = i + 1; j < n; ++j) { /* Find the rightmost element which is smaller than the sum of two fixed elements. The important thing to note here is, we use the previous value of k. If value of arr[i] + arr[j-1] was greater than arr[k], then arr[i] + arr[j] must be greater than k, because the array is sorted. */ while (k < n && arr[i] + arr[j] > arr[k]) ++k; /* Total number of possible triangles that can be formed with the two fixed elements is k - j - 1. The two fixed elements are arr[i] and arr[j]. All elements between arr[j+1] to arr[k-1] can form a triangle with arr[i] and arr[j]. One is subtracted from k because k is incremented one extra in above while loop. k will always be greater than j. If j becomes equal to k, then above loop will increment k, because arr[k] + arr[i] is always/ greater than arr[k] */ if (k > j) count += k - j - 1; } } return count; } // Driver Code public static void Main() { int [] arr = { 10, 21, 22, 100, 101, 200, 300 }; Console.WriteLine( "Total number of triangles is " + findNumberOfTriangles(arr)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to count number // of triangles that can be // formed from given array // Function to count all // possible triangles with // arr[] element function findNumberOfTriangles( $arr ) { $n = count ( $arr ); // Sort the array elements // in non-decreasing order sort( $arr ); // Initialize count // of triangles $count = 0; // Fix the first element. // We need to run till n-3 // as the other two elements // are selected from // arr[i+1...n-1] for ( $i = 0; $i < $n - 2; ++ $i ) { // Initialize index of the // rightmost third element $k = $i + 2; // Fix the second element for ( $j = $i + 1; $j < $n ; ++ $j ) { /* Find the rightmost element which is smaller than the sum of two fixed elements. The important thing to note here is, we use the previous value of k. If value of arr[i] + arr[j-1] was greater than arr[k], then arr[i] + arr[j] must be greater than k, because the array is sorted. */ while ( $k < $n && $arr [ $i ] + $arr [ $j ] > $arr [ $k ]) ++ $k ; /* Total number of possible triangles that can be formed with the two fixed elements is k - j - 1. The two fixed elements are arr[i] and arr[j]. All elements between arr[j+1] to arr[k-1] can form a triangle with arr[i] and arr[j]. One is subtracted from k because k is incremented one extra in above while loop. k will always be greater than j. If j becomes equal to k, then above loop will increment k, because arr[k] + arr[i] is always/ greater than arr[k] */ if ( $k > $j ) $count += $k - $j - 1; } } return $count ; } // Driver code $arr = array (10, 21, 22, 100, 101, 200, 300); echo "Total number of triangles is " , findNumberOfTriangles( $arr ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to count number of triangles that can be // formed from given array // Function to count all possible triangles with arr[] // elements function findNumberOfTriangles(arr) { let n = arr.length; // Sort the array elements in non-decreasing order arr.sort((a, b) => a-b); // Initialize count of triangles let count = 0; // Fix the first element. We // need to run till n-3 as // the other two elements are // selected from arr[i+1...n-1] for (let i = 0; i < n - 2; ++i) { // Initialize index of the // rightmost third element let k = i + 2; // Fix the second element for (let j = i + 1; j < n; ++j) { // Find the rightmost element which is // smaller than the sum of two fixed elements // The important thing to note here is, we // use the previous value of k. If value of // arr[i] + arr[j-1] was greater than arr[k], // then arr[i] + arr[j] must be greater than k, // because the array is sorted. while (k < n && arr[i] + arr[j] > arr[k]) ++k; // Total number of possible triangles that can // be formed with the two fixed elements is // k - j - 1. The two fixed elements are arr[i] // and arr[j]. All elements between arr[j+1]/ to // arr[k-1] can form a triangle with arr[i] and arr[j]. // One is subtracted from k because k is incremented // one extra in above while loop. // k will always be greater than j. If j becomes equal // to k, then above loop will increment k, because arr[k] // + arr[i] is always greater than arr[k] if (k > j) count += k - j - 1; } } return count; } // Driver code let arr = [ 10, 21, 22, 100, 101, 200, 300 ]; let size = arr.length; document.write( "Total number of triangles possible is " + findNumberOfTriangles(arr, size)); // This code is contributed by Manoj </script> |
输出：
Total number of triangles possible is 6
- 复杂性分析：
- 时间复杂性： O（n^2）。 由于3个嵌套循环，时间复杂度看起来更高。可以观察到，k在最外层的循环中只初始化了一次。对于最外层循环的每次迭代，最内层循环的执行时间最多为O（n），因为k从i+2开始，对于j的所有值，都上升到n。因此，时间复杂度为O（n^2）。
- 空间复杂性： O（1）。 不需要额外的空间。所以空间复杂性是恒定的
方法3： 使用 双指针方法 在两个嵌套循环中。
- 方法： 首先对数组进行排序，运行一个嵌套循环，修复一个索引，然后尝试修复一个上下索引，在这个索引中，我们可以使用所有长度与该固定索引形成一个三角形。
- 算法：
- 对数组进行排序，然后取三个变量l、r和i，分别指向开始、结束-1和从数组末尾开始的数组元素。
- 从末尾（n-1到1）遍历数组，每次迭代都保持l=0和r=i-1的值
- 现在，如果可以用arr[l]和arr[r]形成三角形，那么三角形显然可以形成 从[l+1]到[l+2]…。。a[r-1]，arr[r]和a[i]， 因为数组已排序 ，可使用（r-l）直接计算。然后减小r的值，继续循环直到l小于r
- 如果不能使用arr[l]和arr[r]形成三角形，则增加l的值，并继续循环，直到l小于r
- 所以迭代的总体复杂性 通过所有数组元素减少。
- 实施：
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; void CountTriangles(vector< int > A) { int n = A.size(); sort(A.begin(), A.end()); int count = 0; for ( int i = n - 1; i >= 1; i--) { int l = 0, r = i - 1; while (l < r) { if (A[l] + A[r] > A[i]) { // If it is possible with a[l], a[r] // and a[i] then it is also possible // with a[l+1]..a[r-1], a[r] and a[i] count += r - l; // checking for more possible solutions r--; } else // if not possible check for // higher values of arr[l] l++; } } cout << "No of possible solutions: " << count; } int main() { vector< int > A = { 4, 3, 5, 7, 6 }; CountTriangles(A); } |
JAVA
// Java implementation of the above approach import java.util.*; class GFG { static void CountTriangles( int [] A) { int n = A.length; Arrays.sort(A); int count = 0 ; for ( int i = n - 1 ; i >= 1 ; i--) { int l = 0 , r = i - 1 ; while (l < r) { if (A[l] + A[r] > A[i]) { // If it is possible with a[l], a[r] // and a[i] then it is also possible // with a[l+1]..a[r-1], a[r] and a[i] count += r - l; // checking for more possible solutions r--; } else // if not possible check for // higher values of arr[l] { l++; } } } System.out.print( "No of possible solutions: " + count); } // Driver Code public static void main(String[] args) { int [] A = { 4 , 3 , 5 , 7 , 6 }; CountTriangles(A); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python implementation of the above approach def CountTriangles( A): n = len (A); A.sort(); count = 0 ; for i in range (n - 1 , 0 , - 1 ): l = 0 ; r = i - 1 ; while (l < r): if (A[l] + A[r] > A[i]): # If it is possible with a[l], a[r] # and a[i] then it is also possible # with a[l + 1]..a[r-1], a[r] and a[i] count + = r - l; # checking for more possible solutions r - = 1 ; else : # if not possible check for # higher values of arr[l] l + = 1 ; print ( "No of possible solutions: " , count); # Driver Code if __name__ = = '__main__' : A = [ 4 , 3 , 5 , 7 , 6 ]; CountTriangles(A); # This code is contributed by PrinciRaj1992 |
C#
// C# implementation of the above approach using System; class GFG { static void CountTriangles( int [] A) { int n = A.Length; Array.Sort(A); int count = 0; for ( int i = n - 1; i >= 1; i--) { int l = 0, r = i - 1; while (l < r) { if (A[l] + A[r] > A[i]) { // If it is possible with a[l], a[r] // and a[i] then it is also possible // with a[l+1]..a[r-1], a[r] and a[i] count += r - l; // checking for more possible solutions r--; } else // if not possible check for // higher values of arr[l] { l++; } } } Console.Write( "No of possible solutions: " + count); } // Driver Code public static void Main(String[] args) { int [] A = { 4, 3, 5, 7, 6 }; CountTriangles(A); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript implementation of the above approach function CountTriangles(A) { var n = A.length; A.sort(); var count = 0; for (i = n - 1; i >= 1; i--) { var l = 0, r = i - 1; while (l < r) { if (A[l] + A[r] > A[i]) { // If it is possible with a[l], a[r] // and a[i] then it is also possible // with a[l+1]..a[r-1], a[r] and a[i] count += r - l; // checking for more possible solutions r--; } else // if not possible check for // higher values of arr[l] { l++; } } } document.write( "No of possible solutions: " + count); } // Driver Code var A = [ 4, 3, 5, 7, 6 ]; CountTriangles(A); // This code is contributed by aashish1995 </script> |
输出：
No of possible solutions: 9
- 复杂性分析：
- 时间复杂性： O（n^2）。 由于使用了两个嵌套循环，与上述方法相比，整体迭代次数大大减少。
- 空间复杂性： O（1）。 由于不需要额外的空间，所以空间复杂度是恒定的
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
