给定一个不同整数数组和一个和值。打印总和小于给定总和值的所有三元组。预期时间复杂度为O（n 2. ).
null
例子 :
Input : arr[] = {-2, 0, 1, 3} sum = 2.Output : (-2, 0, 1) (-2, 0, 3) Explanation : The two triplets have sum less than 2.Input : arr[] = {5, 1, 3, 4, 7} sum = 12.Output : (1, 3, 4) (1, 3, 5) (1, 3, 7) (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 printTriplets( int arr[], int n, int sum) { // 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) cout << arr[i] << ", " << arr[j] << ", " << arr[k] << endl; } } } // Driver program int main() { int arr[] = {5, 1, 3, 4, 7}; int n = sizeof arr / sizeof arr[0]; int sum = 12; printTriplets(arr, n, sum); return 0; } |
JAVA
// A Simple Java program to // count triplets with sum // smaller than a given value import java.io.*; class GFG { static int printTriplets( int arr[], int n, int sum) { // 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) System.out.println(arr[i] + ", " + arr[j] + ", " + arr[k]); } } return 0 ; } // Driver Code public static void main (String[] args) { int arr[] = { 5 , 1 , 3 , 4 , 7 }; int n = arr.length; int sum = 12 ; printTriplets(arr, n, sum); } } // This code is contributed // by anuj_67. |
Python3
# A Simple python 3 program to count # triplets with sum smaller than a # given value def printTriplets(arr, n, sum ): # Fix the first element as A[i] for i in range ( 0 , n - 2 , 1 ): # Fix the second element as A[j] for j in range (i + 1 , n - 1 , 1 ): # Now look for the third number for k in range (j + 1 , n, 1 ): if (arr[i] + arr[j] + arr[k] < sum ): print (arr[i], "," , arr[j], "," , arr[k]) # Driver Code if __name__ = = '__main__' : arr = [ 5 , 1 , 3 , 4 , 7 ] n = len (arr) sum = 12 printTriplets(arr, n, sum ) # This code is contributed by # Sahil_Shelangia |
C#
// A Simple C# program to // count triplets with sum // smaller than a given value using System; class GFG { static int printTriplets( int [] arr, int n, int sum) { // 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) Console.WriteLine(arr[i] + ", " + arr[j] + ", " + arr[k]); } } return 0; } // Driver Code public static void Main () { int [] arr = {5, 1, 3, 4, 7}; int n = arr.Length; int sum = 12; printTriplets(arr, n, sum); } } // This code is contributed // by Mukul Singh. |
PHP
<?php // A Simple PHP program to count triplets // with sum smaller than a given value function printTriplets(& $arr , $n , $sum ) { // Fix the first element as A[i] for ( $i = 0; $i < $n - 2; $i ++) { // Fix the second element as A[j] for ( $j = $i + 1; $j < $n - 1; $j ++) { // Now look for the third number for ( $k = $j + 1; $k < $n ; $k ++) if ( $arr [ $i ] + $arr [ $j ] + $arr [ $k ] < $sum ) { echo ( $arr [ $i ]); echo ( ", " ); echo ( $arr [ $j ]); echo ( ", " ); echo ( $arr [ $k ]); echo ( "" ); } } } } // Driver Code $arr = array (5, 1, 3, 4, 7); $n = sizeof( $arr ); $sum = 12; printTriplets( $arr , $n , $sum ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // A Simple JavaScript program to // count triplets with sum // smaller than a given value function printTriplets(arr, n, sum) { // 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) document.write(arr[i] + ", " + arr[j] + ", " + arr[k] + "<br>" ); } } } // Driver program let arr = [5, 1, 3, 4, 7]; let n = arr.length; let sum = 12; printTriplets(arr, n, sum); // This code is contributed by Surbhi Tyagi. </script> |
输出：
5, 1, 35, 1, 41, 3, 41, 3, 7
上述解的时间复杂度为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 = sum), then do k-- // Else for current i and j, there are (k-j) possible // third elements that satisfy the constraint. (ii) Else print elements from j to k
下面是上述想法的实现。
C++
// C++ program to print triplets with sum smaller // than a given value #include <bits/stdc++.h> using namespace std; int printTriplets( int arr[], int n, int sum) { // Sort input array sort(arr, arr + n); // 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 are total k-j third elements. for ( int x = j + 1; x <= k; x++) cout << arr[i] << ", " << arr[j] << ", " << arr[x] << endl; j++; } } } } // Driver program int main() { int arr[] = { 5, 1, 3, 4, 7 }; int n = sizeof arr / sizeof arr[0]; int sum = 12; printTriplets(arr, n, sum); return 0; } |
JAVA
// Java program to print // triplets with sum smaller // than a given value import java.util.*; import java.lang.*; import java.io.*; class GFG { static void printTriplets( int arr[], int n, int sum) { // Sort input array Arrays.sort(arr); // 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 // are total k-j third elements. for ( int x = j + 1 ; x <= k; x++) System.out.println(arr[i] + ", " + arr[j] + ", " + arr[x]); j++; } } } } // Driver Code public static void main(String args[]) { int arr[] = { 5 , 1 , 3 , 4 , 7 }; int n = arr.length; int sum = 12 ; printTriplets(arr, n, sum); } } // This code is contributed // by Subhadeep |
Python3
# Python3 program to print # triplets with sum smaller # than a given value def printTriplets(arr, n, sum ): # Sort input array arr.sort() # Every iteration of loop # counts triplet with # first element as arr[i]. for i in range (n - 2 ): # Initialize other two elements # as corner elements of subarray # arr[j+1..k] (j, k) = (i + 1 , 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 - = 1 # Else move left corner else : # This is important. For # current i and j, there # are total k-j third elements. for x in range (j + 1 , k + 1 ): print ( str (arr[i]) + ", " + str (arr[j]) + ", " + str (arr[x])) j + = 1 # Driver code if __name__ = = "__main__" : arr = [ 5 , 1 , 3 , 4 , 7 ] n = len (arr) sum = 12 printTriplets(arr, n, sum ); # This code is contributed by rutvik_56 |
C#
// C# program to print // triplets with sum smaller // than a given value using System; class GFG { static void printTriplets( int [] arr, int n, int sum) { // Sort input array Array.Sort(arr); // 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 // are total k-j third elements. for ( int x = j + 1; x <= k; x++) Console.WriteLine(arr[i] + ", " + arr[j] + ", " + arr[x]); j++; } } } } // Driver Code public static void Main() { int [] arr = { 5, 1, 3, 4, 7 }; int n = arr.Length; int sum = 12; printTriplets(arr, n, sum); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP program to print triplets with // sum smaller than a given value function printTriplets( $arr , $n , $sum ) { // Sort input array sort( $arr , 0); // Every iteration of loop counts // triplet with first element as arr[i]. for ( $i = 0; $i < $n - 2; $i ++) { // 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 --; // Else move left corner else { // This is important. For current i and j, // there are total k-j third elements. for ( $x = $j + 1; $x <= $k ; $x ++) echo $arr [ $i ] . ", " . $arr [ $j ] . ", " . $arr [ $x ] . "" ; $j ++; } } } } // Driver Code $arr = array (5, 1, 3, 4, 7); $n = sizeof( $arr ); $sum = 12; printTriplets( $arr , $n , $sum ); // This code is contributed // by Akanksha Rai ?> |
Javascript
<script> // JavaScript program to print // triplets with sum smaller // than a given value function printTriplets(arr, n, sum) { // Sort input array arr.sort( function (a, b){ return a - b}); // 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 // are total k-j third elements. for (let x = j + 1; x <= k; x++) document.write(arr[i] + ", " + arr[j] + ", " + arr[x] + "</br>" ); j++; } } } } let arr = [ 5, 1, 3, 4, 7 ]; let n = arr.length; let sum = 12; printTriplets(arr, n, sum); </script> |
输出：
1, 3, 41, 3, 51, 3, 71, 4, 5
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
