给定一个不同整数数组和一个和值。求和小于给定和值的三胞胎数。预期的时间复杂度为O（n） 2. ). 例如：
null
Input : arr[] = {-2, 0, 1, 3} sum = 2.Output : 2Explanation : Below are triplets with sum less than 2 (-2, 0, 1) and (-2, 0, 3) Input : arr[] = {5, 1, 3, 4, 7} sum = 12.Output : 4Explanation : Below are triplets with sum less than 12 (1, 3, 4), (1, 3, 5), (1, 3, 7) and (1, 4, 5)
A. 简单解决方案 是运行三个循环来逐个考虑所有三元组。对于每个三元组，如果三元组之和小于给定之和，则比较总和和增量计数。
C++
// A Simple C++ program to count triplets with sum smaller // than a given value #include<bits/stdc++.h> using namespace std; int countTriplets( int arr[], int n, int sum) { // Initialize result int ans = 0; // Fix the first element as A[i] for ( int i = 0; i < n-2; i++) { // Fix the second element as A[j] for ( int j = i+1; j < n-1; j++) { // Now look for the third number for ( int k = j+1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) ans++; } } return ans; } // Driver program int main() { int arr[] = {5, 1, 3, 4, 7}; int n = sizeof arr / sizeof arr[0]; int sum = 12; cout << countTriplets(arr, n, sum) << endl; return 0; } |
JAVA
// A Simple Java program to count triplets with sum smaller // than a given value class Test { static int arr[] = new int []{ 5 , 1 , 3 , 4 , 7 }; static int countTriplets( int n, int sum) { // Initialize result int ans = 0 ; // Fix the first element as A[i] for ( int i = 0 ; i < n- 2 ; i++) { // Fix the second element as A[j] for ( int j = i+ 1 ; j < n- 1 ; j++) { // Now look for the third number for ( int k = j+ 1 ; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) ans++; } } return ans; } // Driver method to test the above function public static void main(String[] args) { int sum = 12 ; System.out.println(countTriplets(arr.length, sum)); } } |
Python 3
# A Simple Python 3 program to count triplets with sum smaller # than a given value #include<bits/stdc++.h> def countTriplets(arr, n, sum ): # Initialize result ans = 0 # Fix the first element as A[i] for i in range ( 0 ,n - 2 ): # Fix the second element as A[j] for j in range ( i + 1 ,n - 1 ): # Now look for the third number for k in range ( j + 1 , n): if (arr[i] + arr[j] + arr[k] < sum ): ans + = 1 return ans # Driver program arr = [ 5 , 1 , 3 , 4 , 7 ] n = len (arr) sum = 12 print (countTriplets(arr, n, sum )) #Contributed by Smitha |
C#
// A Simple C# program to count triplets with sum smaller // than a given value using System; class Test { static int [] arr = new int []{5, 1, 3, 4, 7}; static int countTriplets( int n, int sum) { // Initialize result int ans = 0; // Fix the first element as A[i] for ( int i = 0; i < n-2; i++) { // Fix the second element as A[j] for ( int j = i+1; j < n-1; j++) { // Now look for the third number for ( int k = j+1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) ans++; } } return ans; } // Driver method to test the above function public static void Main() { int sum = 12; Console.Write(countTriplets(arr.Length, sum)); } } |
Javascript
<script> // A Simple Javascript program to count triplets with sum smaller // than a given value let arr = [5, 1, 3, 4, 7]; function countTriplets(n,sum) { // Initialize result let ans = 0; // Fix the first element as A[i] for (let i = 0; i < n-2; i++) { // Fix the second element as A[j] for (let j = i + 1; j < n-1; j++) { // Now look for the third number for (let k = j + 1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) ans++; } } return ans; } // Driver method to test the above function let sum = 12; document.write(countTriplets(arr.length, sum)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
4
上述解的时间复杂度为O（n） 3. ).安 有效解决方案 可以在O（n）中计数三胞胎 2. )首先对数组进行排序，然后使用 这 在一个循环中发布。
1) Sort the input array in increasing order.2) Initialize result as 0.3) Run a loop from i = 0 to n-2. An iteration of this loop finds all triplets with arr[i] as first element. a) Initialize other two elements as corner elements of subarray arr[i+1..n-1], i.e., j = i+1 and k = n-1 b) Move j and k toward each other until they meet, i.e., while (j<k), (i) If arr[i] + arr[j] + arr[k] >= sum then k-- // Else for current i and j, there can (k-j) possible third elements // that satisfy the constraint. (ii) Else Do ans += (k - j) followed by j++
下面是上述想法的实施。
C++
// C++ program to count triplets with sum smaller than a given value #include<bits/stdc++.h> using namespace std; int countTriplets( int arr[], int n, int sum) { // Sort input array sort(arr, arr+n); // Initialize result int ans = 0; // Every iteration of loop counts triplet with // first element as arr[i]. for ( int i = 0; i < n - 2; i++) { // Initialize other two elements as corner elements // of subarray arr[j+1..k] int j = i + 1, k = n - 1; // Use Meet in the Middle concept while (j < k) { // If sum of current triplet is more or equal, // move right corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For current i and j, there // can be total k-j third elements. ans += (k - j); j++; } } } return ans; } // Driver program int main() { int arr[] = {5, 1, 3, 4, 7}; int n = sizeof arr / sizeof arr[0]; int sum = 12; cout << countTriplets(arr, n, sum) << endl; return 0; } |
JAVA
// A Simple Java program to count triplets with sum smaller // than a given value import java.util.Arrays; class Test { static int arr[] = new int []{ 5 , 1 , 3 , 4 , 7 }; static int countTriplets( int n, int sum) { // Sort input array Arrays.sort(arr); // Initialize result int ans = 0 ; // Every iteration of loop counts triplet with // first element as arr[i]. for ( int i = 0 ; i < n - 2 ; i++) { // Initialize other two elements as corner elements // of subarray arr[j+1..k] int j = i + 1 , k = n - 1 ; // Use Meet in the Middle concept while (j < k) { // If sum of current triplet is more or equal, // move right corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For current i and j, there // can be total k-j third elements. ans += (k - j); j++; } } } return ans; } // Driver method to test the above function public static void main(String[] args) { int sum = 12 ; System.out.println(countTriplets(arr.length, sum)); } } |
Python3
# Python3 program to count triplets with # sum smaller than a given value # Function to count triplets with sum smaller # than a given value def countTriplets(arr,n, sum ): # Sort input array arr.sort() # Initialize result ans = 0 # Every iteration of loop counts triplet with # first element as arr[i]. for i in range ( 0 ,n - 2 ): # Initialize other two elements as corner elements # of subarray arr[j+1..k] j = i + 1 k = n - 1 # Use Meet in the Middle concept while (j < k): # If sum of current triplet is more or equal, # move right corner to look for smaller values if (arr[i] + arr[j] + arr[k] > = sum ): k = k - 1 # Else move left corner else : # This is important. For current i and j, there # can be total k-j third elements. ans + = (k - j) j = j + 1 return ans # Driver program if __name__ = = '__main__' : arr = [ 5 , 1 , 3 , 4 , 7 ] n = len (arr) sum = 12 print (countTriplets(arr, n, sum )) # This code is contributed by # Yatin Gupta |
C#
// A Simple C# program to count // triplets with sum smaller // than a given value using System; class GFG { static int []arr = new int []{5, 1, 3, 4, 7}; static int countTriplets( int n, int sum) { // Sort input array Array.Sort(arr); // Initialize result int ans = 0; // Every iteration of loop // counts triplet with // first element as arr[i]. for ( int i = 0; i < n - 2; i++) { // Initialize other two // elements as corner elements // of subarray arr[j+1..k] int j = i + 1, k = n - 1; // Use Meet in the Middle concept while (j < k) { // If sum of current triplet // is more or equal, move right // corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For // current i and j, there // can be total k-j third elements. ans += (k - j); j++; } } } return ans; } // Driver Code public static void Main() { int sum = 12; Console.Write(countTriplets(arr.Length, sum)); } } // This code is contributed by Smitha |
Javascript
<script> // A Simple Javascript program to count triplets with sum smaller // than a given value let arr = [5, 1, 3, 4, 7]; function countTriplets(n,sum) { // Sort input array arr.sort( function (a,b){ return b-a}); // Initialize result let ans = 0; // Every iteration of loop counts triplet with // first element as arr[i]. for (let i = 0; i < n - 2; i++) { // Initialize other two elements as corner elements // of subarray arr[j+1..k] let j = i + 1, k = n - 1; // Use Meet in the Middle concept while (j < k) { // If sum of current triplet is more or equal, // move right corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For current i and j, there // can be total k-j third elements. ans += (k - j); j++; } } } return ans; } // Driver method to test the above function let sum = 12; document.write(countTriplets(arr.length, sum)); // This code is contributed by rag2127 </script> |
输出：
4
感谢Gaurav Ahirwar提出这个解决方案。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
