計算可能的三角形數量 · GeeksForGeeks 中文系列教程

# 計算可能的三角形數量 > 原文： [https://www.geeksforgeeks.org/find-number-of-triangles-possible/](https://www.geeksforgeeks.org/find-number-of-triangles-possible/) 給定一個未排序的正整數數組，找到可以用三個不同的數組元素作為三角形的三個邊形成的三角形的數量。為了使三角形有 3 個值，兩個值（或邊）中的任何一個之和必須大于第三個值（或第三邊）。 **示例**： ``` Input: arr= {4, 6, 3, 7} Output: 3 Explanation: 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: 6 Explanation: 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（暴力）** * **方法**：暴力方法是運行三個循環并跟蹤到目前為止可能出現的三角形數量。三個循環從數組中選擇三個不同的值。最內層的循環檢查是否有三角形屬性，該屬性指定任意兩個邊的和必須大于第三邊的值。 * **算法**： 1. 運行三個嵌套循環，每個循環從上一個循環的索引開始到數組的末尾，即從 0 到 n 運行第一個循環，從 i 到 n 循環 j，從 j 到 n 循環 k。 2. 檢查 array [i] + array [j] > array [k]，array [i] + array [k] > array [j]，array [k] + array [j] > array [ i]，即兩側的和大于第三側 3. 如果所有三個條件都匹配，則增加計數。 4. 打印計數 * **實現**： ## 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) ????{ ????????// 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 ?????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 ``` ## 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 ``` * **輸出**： ``` Total number of triangles possible is 6 ``` * **復雜度分析**： * **時間復雜度**： O（N ^ 3），其中 N 是輸入數組的大小。 * **空間復雜度**：`O(1)` **方法 2** ：這是一種復雜而有效的方法，可以將時間復雜度從 **O（n ^ 3）**降低到 **O（n ^ 2）** ，三角形的兩個邊固定，并且可以使用這兩個邊找到計數。 * **方法**：首先以升序對數組進行排序。然后使用兩個循環。固定第一個側面的外環和固定第二個側面的內環，然后找到長度小于其他兩個側面的第三側面的最遠索引（大于兩個側面的索引）。因此，可以找到一系列值的第三邊，可以保證其長度大于其他各個邊但小于兩個邊的總和。 * **Algorithm:** Let a, b and c be three sides. The below condition must hold for a triangle (sum of two sides is greater than the third side) i) a + b > c ii) b + c > a iii) a + c > b 以下是計算三角形的步驟。 1. 以升序對數組進行排序。 2. 現在運行一個嵌套循環。外循環從頭到尾運行，內循環從第一個循環的*索引+ 1* 到末尾運行。以第一循環的循環計數器為 *i* ，第二循環的循環計數器為 *j* 。取另一個變量 *k = i + 2* 3. 現在有兩個指針 *i* 和 *j* ，其中 *array [i]* 和 *array [j]* 表示三角形的兩個邊。對于固定的 *i* 和 *j* ，找到將滿足三角形條件的第三邊的數量。即找到 *array [k]* 的最大值，使得 *array [i]* + *array [j]* > *array [k]* 4. 因此，當我們獲得最大值時，則第三方的計數為 *k – j* ，然后將其加到總計數中。 5. 現在總結 *i* 和 *j* 的所有有效對，其中 *i < j* * **實現**： ## 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*/ ``` ## Python ``` # 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\. ?> ``` * **輸出**： ``` 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**：僅在兩個嵌套循環中使用**兩個指針方法**，可以大大降低時間復雜度。 * **方法**：首先對數組進行排序，然后運行一個嵌套循環，修復一個索引，然后嘗試修復一個上下索引，在其中我們可以使用所有長度來與該固定索引形成一個三角形。 * **算法**： 1. 對數組進行排序，然后取三個變量 l，r 和 i，分別指向 start，end-1 和從數組末尾開始的數組元素。 2. 從末端（n-1 到 1）遍歷數組，對于每次迭代，保持 l = 0 和 r = i-1 的值 3. 現在，如果可以使用 arr [l]和 arr [r]形成三角形，那么顯然可以從 a [l + 1]，a [l + 2] ..... a [r-1]，arr 形成三角形 [r]和 a [i]，**，因為該數組已排序**，可以使用（rl）直接計算該數組。然后遞減 r 的值并繼續循環直到 l 小于 r 4. 如果不能使用 arr [l]和 arr [r]形成三角形，則增加 r 的值并繼續循環直到 l 小于 r 5. 因此，降低了遍歷所有數組元素的的總體復雜性。 * **實現**： ## 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 ``` * **輸出**： ``` No of possible solutions: 9 ``` * **復雜度分析**： * **時間復雜度**： O（n ^ 2）。由于使用了兩個嵌套循環，但是與上述方法相比，整體迭代大大減少了。 * **空間復雜度**：`O(1)`。由于不需要額外的空間，因此空間復雜度是恒定的來源： [http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers](http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers) [https://www.geeksforgeeks.org/two-pointers-technique/](https://www.geeksforgeeks.org/two-pointers-technique/)