给定一个不同正整数的排序数组，打印构成AP（或算术级数）的所有三元组 例如：
null
Input : arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 };Output :6 9 122 12 2212 17 222 17 3212 22 329 22 352 22 4222 32 42Input : arr[] = { 3, 5, 6, 7, 8, 10, 12};Output :3 5 75 6 76 7 86 8 108 10 12
A. 简单解决方案 就是运行三个嵌套循环来生成所有的三元组，对于每个三元组，检查它是否形成AP。该解的时间复杂度为O（n） 3. ) A. 更好的解决方案 就是使用散列。我们从左到右遍历数组。我们把每个元素作为中间元素，然后将其作为下一个元素。为了搜索前一个元素，我们使用了一个哈希表。
C++
// C++ program to print all triplets in given // array that form Arithmetic Progression // C++ program to print all triplets in given // array that form Arithmetic Progression #include <bits/stdc++.h> using namespace std; // Function to print all triplets in // given sorted array that forms AP void printAllAPTriplets( int arr[], int n) { unordered_set< int > s; for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // Use hash to find if there is // a previous element with difference // equal to arr[j] - arr[i] int diff = arr[j] - arr[i]; if (s.find(arr[i] - diff) != s.end()) cout << arr[i] - diff << " " << arr[i] << " " << arr[j] << endl; } s.insert(arr[i]); } } // Driver code int main() { int arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 }; int n = sizeof (arr) / sizeof (arr[0]); printAllAPTriplets(arr, n); return 0; } |
JAVA
// Java program to print all // triplets in given array // that form Arithmetic // Progression import java.io.*; import java.util.*; class GFG { // Function to print // all triplets in // given sorted array // that forms AP static void printAllAPTriplets( int []arr, int n) { ArrayList<Integer> s = new ArrayList<Integer>(); for ( int i = 0 ; i < n - 1 ; i++) { for ( int j = i + 1 ; j < n; j++) { // Use hash to find if // there is a previous // element with difference // equal to arr[j] - arr[i] int diff = arr[j] - arr[i]; boolean exists = s.contains(arr[i] - diff); if (exists) System.out.println(arr[i] - diff + " " + arr[i] + " " + arr[j]); } s.add(arr[i]); } } // Driver code public static void main(String args[]) { int []arr = { 2 , 6 , 9 , 12 , 17 , 22 , 31 , 32 , 35 , 42 }; int n = arr.length; printAllAPTriplets(arr, n); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python program to print all # triplets in given array # that form Arithmetic # Progression # Function to print # all triplets in # given sorted array # that forms AP def printAllAPTriplets(arr, n) : s = []; for i in range ( 0 , n - 1 ) : for j in range (i + 1 , n) : # Use hash to find if # there is a previous # element with difference # equal to arr[j] - arr[i] diff = arr[j] - arr[i]; if ((arr[i] - diff) in arr) : print ( "{} {} {}" . format ((arr[i] - diff), arr[i], arr[j]), end = "" ); s.append(arr[i]); # Driver code arr = [ 2 , 6 , 9 , 12 , 17 , 22 , 31 , 32 , 35 , 42 ]; n = len (arr); printAllAPTriplets(arr, n); # This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# program to print all // triplets in given array // that form Arithmetic // Progression using System; using System.Collections.Generic; class GFG { // Function to print // all triplets in // given sorted array // that forms AP static void printAllAPTriplets( int []arr, int n) { List< int > s = new List< int >(); for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // Use hash to find if // there is a previous // element with difference // equal to arr[j] - arr[i] int diff = arr[j] - arr[i]; bool exists = s.Exists(element => element == (arr[i] - diff)); if (exists) Console.WriteLine(arr[i] - diff + " " + arr[i] + " " + arr[j]); } s.Add(arr[i]); } } // Driver code static void Main() { int []arr = new int []{ 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 }; int n = arr.Length; printAllAPTriplets(arr, n); } } // This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php // PHP program to pr$all // triplets in given array // that form Arithmetic // Progression // Function to print // all triplets in // given sorted array // that forms AP function printAllAPTriplets( $arr , $n ) { $s = array (); for ( $i = 0; $i < $n - 1; $i ++) { for ( $j = $i + 1; $j < $n ; $j ++) { // Use hash to find if // there is a previous // element with difference // equal to arr[j] - arr[i] $diff = $arr [ $j ] - $arr [ $i ]; if (in_array( $arr [ $i ] - $diff , $arr )) echo (( $arr [ $i ] - $diff ) . " " . $arr [ $i ] . " " . $arr [ $j ] . "" ); } array_push ( $s , $arr [ $i ]); } } // Driver code $arr = array (2, 6, 9, 12, 17, 22, 31, 32, 35, 42); $n = count ( $arr ); printAllAPTriplets( $arr , $n ); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Javascript
<script> // JavaScript program to print all triplets in given // array that form Arithmetic Progression // Function to print all triplets in // given sorted array that forms AP function printAllAPTriplets( arr, n){ const s = new Set() for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { // Use hash to find if there is // a previous element with difference // equal to arr[j] - arr[i] let diff = arr[j] - arr[i]; if (s.has(arr[i] - diff)) document.write(arr[i] - diff + " " + arr[i] + " " + arr[j] + "<br>" ); } s.add(arr[i]); } } // Driver code let arr = [ 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 ]; let n = arr.length; printAllAPTriplets(arr, n); </script> |
输出：
6 9 122 12 2212 17 222 17 3212 22 329 22 352 22 4222 32 42
时间复杂性： O（n） 2. ) 辅助空间： O（n） 一 有效解决方案 基于数组已排序的事实。我们使用的概念与中讨论的相同 GP三重问题 。其想法是从第二个元素开始，将每个元素固定为中间元素，并在三元组中搜索其他两个元素（一个较小，一个较大）。 下面是上述想法的实施。
C++
// C++ program to print all triplets in given // array that form Arithmetic Progression #include <bits/stdc++.h> using namespace std; // Function to print all triplets in // given sorted array that forms AP void printAllAPTriplets( int arr[], int n) { for ( int i = 1; i < n - 1; i++) { // Search other two elements of // AP with arr[i] as middle. for ( int j = i - 1, k = i + 1; j >= 0 && k < n;) { // if a triplet is found if (arr[j] + arr[k] == 2 * arr[i]) { cout << arr[j] << " " << arr[i] << " " << arr[k] << endl; // Since elements are distinct, // arr[k] and arr[j] cannot form // any more triplets with arr[i] k++; j--; } // If middle element is more move to // higher side, else move lower side. else if (arr[j] + arr[k] < 2 * arr[i]) k++; else j--; } } } // Driver code int main() { int arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 }; int n = sizeof (arr) / sizeof (arr[0]); printAllAPTriplets(arr, n); return 0; } |
JAVA
// Java implementation to print // all the triplets in given array // that form Arithmetic Progression import java.io.*; class GFG { // Function to print all triplets in // given sorted array that forms AP static void findAllTriplets( int arr[], int n) { for ( int i = 1 ; i < n - 1 ; i++) { // Search other two elements // of AP with arr[i] as middle. for ( int j = i - 1 , k = i + 1 ; j >= 0 && k < n;) { // if a triplet is found if (arr[j] + arr[k] == 2 * arr[i]) { System.out.println(arr[j] + " " + arr[i]+ " " + arr[k]); // Since elements are distinct, // arr[k] and arr[j] cannot form // any more triplets with arr[i] k++; j--; } // If middle element is more move to // higher side, else move lower side. else if (arr[j] + arr[k] < 2 * arr[i]) k++; else j--; } } } // Driver code public static void main (String[] args) { int arr[] = { 2 , 6 , 9 , 12 , 17 , 22 , 31 , 32 , 35 , 42 }; int n = arr.length; findAllTriplets(arr, n); } } // This code is contributed by vt_m. |
Python 3
# python 3 program to print all triplets in given # array that form Arithmetic Progression # Function to print all triplets in # given sorted array that forms AP def printAllAPTriplets(arr, n): for i in range ( 1 , n - 1 ): # Search other two elements of # AP with arr[i] as middle. j = i - 1 k = i + 1 while (j > = 0 and k < n ): # if a triplet is found if (arr[j] + arr[k] = = 2 * arr[i]): print (arr[j], " ", arr[i], " ", arr[k]) # Since elements are distinct, # arr[k] and arr[j] cannot form # any more triplets with arr[i] k + = 1 j - = 1 # If middle element is more move to # higher side, else move lower side. elif (arr[j] + arr[k] < 2 * arr[i]): k + = 1 else : j - = 1 # Driver code arr = [ 2 , 6 , 9 , 12 , 17 , 22 , 31 , 32 , 35 , 42 ] n = len (arr) printAllAPTriplets(arr, n) # This article is contributed # by Smitha Dinesh Semwal |
C#
// C# implementation to print // all the triplets in given array // that form Arithmetic Progression using System; class GFG { // Function to print all triplets in // given sorted array that forms AP static void findAllTriplets( int []arr, int n) { for ( int i = 1; i < n - 1; i++) { // Search other two elements // of AP with arr[i] as middle. for ( int j = i - 1, k = i + 1; j >= 0 && k < n;) { // if a triplet is found if (arr[j] + arr[k] == 2 * arr[i]) { Console.WriteLine(arr[j] + " " + arr[i]+ " " + arr[k]); // Since elements are distinct, // arr[k] and arr[j] cannot form // any more triplets with arr[i] k++; j--; } // If middle element is more move to // higher side, else move lower side. else if (arr[j] + arr[k] < 2 * arr[i]) k++; else j--; } } } // Driver code public static void Main () { int []arr = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 }; int n = arr.Length; findAllTriplets(arr, n); } } // This code is contributed by vt_m. |
PHP
<?php // PHP implementation to print // all the triplets in given array // that form Arithmetic Progression // Function to print all triplets in // given sorted array that forms AP function findAllTriplets( $arr , $n ) { for ( $i = 1; $i < $n - 1; $i ++) { // Search other two elements // of AP with arr[i] as middle. for ( $j = $i - 1, $k = $i + 1; $j >= 0 && $k < $n :winking_face: { // if a triplet is found if ( $arr [ $j ] + $arr [ $k ] == 2 * $arr [ $i ]) { echo $arr [ $j ] . " " . $arr [ $i ]. " " . $arr [ $k ] . "" ; // Since elements are distinct, // arr[k] and arr[j] cannot form // any more triplets with arr[i] $k ++; $j --; } // If middle element is more move to // higher side, else move lower side. else if ( $arr [ $j ] + $arr [ $k ] < 2 * $arr [ $i ]) $k ++; else $j --; } } } // Driver code $arr = array (2, 6, 9, 12, 17, 22, 31, 32, 35, 42); $n = count ( $arr ); findAllTriplets( $arr , $n ); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program to print all triplets in given // array that form Arithmetic Progression // Function to print all triplets in // given sorted array that forms AP function printAllAPTriplets(arr, n) { for (let i = 1; i < n - 1; i++) { // Search other two elements of // AP with arr[i] as middle. for (let j = i - 1, k = i + 1; j >= 0 && k < n;) { // if a triplet is found if (arr[j] + arr[k] == 2 * arr[i]) { document.write(arr[j] + " " + arr[i] + " " + arr[k] + "<br>" ); // Since elements are distinct, // arr[k] and arr[j] cannot form // any more triplets with arr[i] k++; j--; } // If middle element is more move to // higher side, else move lower side. else if (arr[j] + arr[k] < 2 * arr[i]) k++; else j--; } } } // Driver code let arr = [ 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 ]; let n = arr.length; printAllAPTriplets(arr, n); // This code is contributed by Surbhi Tyagi. </script> |
输出：
6 9 122 12 2212 17 222 17 3212 22 329 22 352 22 4222 32 42
时间复杂性： O（n） 2. ) 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
