给定一组不同的整数（只考虑正数）和一个数“m”，求出乘积等于“m”的三元组数。 例如：
null
Input: arr[] = { 1, 4, 6, 2, 3, 8} m = 24Output: 3Input: arr[] = { 0, 4, 6, 2, 3, 8} m = 18Output: 0
前面已经讨论过一种具有O（n）额外空间的方法 邮递 在这篇文章中，我们将讨论一种具有O（1）空间复杂性的方法。 方法： 其想法是使用三指针技术：
- 对输入数组进行排序。
- 将第一个元素固定为[i]，其中i是从0到数组大小–2。
- 在确定三元组的第一个元素后，使用 2分球技术。
以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to count such triplets int countTriplets( int arr[], int n, int m) { int count = 0; // Sort the array sort(arr, arr + n); int end, start, mid; // three pointer technique for (end = n - 1; end >= 2; end--) { int start = 0, mid = end - 1; while (start < mid) { // Calculate the product of a triplet long int prod = arr[end] * arr[start] * arr[mid]; // Check if that product is greater than m, // decrement mid if (prod > m) mid--; // Check if that product is smaller than m, // increment start else if (prod < m) start++; // Check if that product is equal to m, // decrement mid, increment start and // increment the count of pairs else if (prod == m) { count++; mid--; start++; } } } return count; } // Drivers code int main() { int arr[] = { 1, 1, 1, 1, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); int m = 1; cout << countTriplets(arr, n, m); return 0; } |
JAVA
// Java implementation of // above approach import java.io.*; import java.util.*; class GFG { // Function to count such triplets static int countTriplets( int arr[], int n, int m) { int count = 0 ; // Sort the array Arrays.sort(arr); int end, start, mid; // three pointer technique for (end = n - 1 ; end >= 2 ; end--) { start = 0 ; mid = end - 1 ; while (start < mid) { // Calculate the product // of a triplet long prod = arr[end] * arr[start] * arr[mid]; // Check if that product // is greater than m, // decrement mid if (prod > m) mid--; // Check if that product // is smaller than m, // increment start else if (prod < m) start++; // Check if that product is equal // to m, decrement mid, increment // start and increment the // count of pairs else if (prod == m) { count++; mid--; start++; } } } return count; } // Driver code public static void main (String[] args) { int []arr = { 1 , 1 , 1 , 1 , 1 , 1 }; int n = arr.length; int m = 1 ; System.out.println(countTriplets(arr, n, m)); } } // This code is contributed // by inder_verma. |
Python3
# Python3 implementation # of above approach # Function to count such triplets def countTriplets(arr, n, m): count = 0 # Sort the array arr.sort() # three pointer technique for end in range (n - 1 , 1 , - 1 ) : start = 0 mid = end - 1 while (start < mid) : # Calculate the product # of a triplet prod = (arr[end] * arr[start] * arr[mid]) # Check if that product is # greater than m, decrement mid if (prod > m): mid - = 1 # Check if that product is # smaller than m, increment start elif (prod < m): start + = 1 # Check if that product is equal # to m, decrement mid, increment # start and increment the count # of pairs elif (prod = = m): count + = 1 mid - = 1 start + = 1 return count # Drivers code if __name__ = = "__main__" : arr = [ 1 , 1 , 1 , 1 , 1 , 1 ] n = len (arr) m = 1 print (countTriplets(arr, n, m)) # This code is contributed # by ChitraNayal |
C#
// C# implementation of above approach using System; class GFG { // Function to count such triplets static int countTriplets( int []arr, int n, int m) { int count = 0; // Sort the array Array.Sort(arr); int end, start, mid; // three pointer technique for (end = n - 1; end >= 2; end--) { start = 0; mid = end - 1; while (start < mid) { // Calculate the product // of a triplet long prod = arr[end] * arr[start] * arr[mid]; // Check if that product // is greater than m, // decrement mid if (prod > m) mid--; // Check if that product // is smaller than m, // increment start else if (prod < m) start++; // Check if that product // is equal to m, // decrement mid, increment // start and increment the // count of pairs else if (prod == m) { count++; mid--; start++; } } } return count; } // Driver code public static void Main (String []args) { int []arr = { 1, 1, 1, 1, 1, 1 }; int n = arr.Length; int m = 1; Console.WriteLine(countTriplets(arr, n, m)); } } // This code is contributed // by Arnab Kundu |
PHP
<?php // PHP implementation of above approach // Function to count such triplets function countTriplets( $arr , $n , $m ) { $count = 0; // Sort the array sort( $arr ); $end ; $start ; $mid ; // three pointer technique for ( $end = $n - 1; $end >= 2; $end --) { $start = 0; $mid = $end - 1; while ( $start < $mid ) { // Calculate the product of a triplet $prod = $arr [ $end ] * $arr [ $start ] * $arr [ $mid ]; // Check if that product is greater than m, // decrement mid if ( $prod > $m ) $mid --; // Check if that product is smaller than m, // increment start else if ( $prod < $m ) $start ++; // Check if that product is equal to m, // decrement mid, increment start and // increment the count of pairs else if ( $prod == $m ) { $count ++; $mid --; $start ++; } } } return $count ; } // Drivers code $arr = array ( 1, 1, 1, 1, 1, 1 ); $n = sizeof( $arr ) / sizeof( $arr [0]); $m = 1; echo countTriplets( $arr , $n , $m ); #This Code is Contributed by ajit ?> |
Javascript
<script> // Javascript implementation of above approach // Function to count such triplets function countTriplets(arr, n, m) { let count = 0; // Sort the array arr.sort( function (a, b){ return a - b}); let end, start, mid; // three pointer technique for (end = n - 1; end >= 2; end--) { start = 0; mid = end - 1; while (start < mid) { // Calculate the product // of a triplet let prod = arr[end] * arr[start] * arr[mid]; // Check if that product // is greater than m, // decrement mid if (prod > m) mid--; // Check if that product // is smaller than m, // increment start else if (prod < m) start++; // Check if that product // is equal to m, // decrement mid, increment // start and increment the // count of pairs else if (prod == m) { count++; mid--; start++; } } } return count; } let arr = [ 1, 1, 1, 1, 1, 1 ]; let n = arr.length; let m = 1; document.write(countTriplets(arr, n, m)); </script> |
输出：
6
时间复杂性： O（N^2） 空间复杂性： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
