# 打印形成 AP 的排序數組中的所有三元組 > 原文： [https://www.geeksforgeeks.org/print-triplets-sorted-array-form-ap/](https://www.geeksforgeeks.org/print-triplets-sorted-array-form-ap/) 給定不同正整數的排序數組，請打印形成 AP（或算術級數）的所有三元組 **示例**： ``` Input : arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 }; Output : 6 9 12 2 12 22 12 17 22 2 17 32 12 22 32 9 22 35 2 22 42 22 32 42 Input : arr[] = { 3, 5, 6, 7, 8, 10, 12}; Output : 3 5 7 5 6 7 6 7 8 6 8 10 8 10 12 ``` 一種簡單的**解決方案**是運行三個嵌套循環以生成所有三元組，并針對每個三元組檢查是否形成 AP。 該解決方案的時間復雜度為 O（n ³ ） **更好的解決方案**是使用哈希。 我們從左到右遍歷數組。 我們將每個元素視為中間元素，并將其后的所有元素視為下一個元素。 要搜索上一個元素，我們使用哈希表。 ## C++ ```cpp // 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 // 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 ```py # 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 = "\n"); ????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# ```cs // 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 // 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] . "\n"); ????????} ????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) ?> ``` **輸出**： ``` 6 9 12 2 12 22 12 17 22 2 17 32 12 22 32 9 22 35 2 22 42 22 32 42 ``` **時間復雜度**： `O(n^2)` **輔助空間**：`O(n)` **有效解決方案**基于對數組進行排序的事實。 我們使用與 [GP 三元組問題](https://www.geeksforgeeks.org/find-all-triplets-in-a-sorted-array-that-forms-geometric-progression/)中討論的相同概念。 這個想法是從第二個元素開始，將每個元素固定為中間元素，然后在一個三元組中搜索另外兩個元素（一個較小一個，另一個較大一個）。 以下是上述想法的實現。 ## 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; } ```