C++程序 打印所有在排序数组中形成等差数列的三元组

给定排序的不同正整数数组，打印所有形成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

运行三重嵌套循环以生成所有三元组，对于每个三元组，检查是否形成等差数列，这是一个 简单的解决方案 。这种解决方案的时间复杂度是O(n 3 )

使用哈希表是 更好的解决方案 。我们从左到右遍历数组。我们将每个元素视为中间元素，其后的所有元素视为下一个元素。为了搜索前一个元素，我们使用哈希表。

// 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;
}  

输出:

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三元组问题，这是一种 高效的解决方案 。从第二个元素开始，将每个元素固定为中间元素，并搜索三元组中的另外两个元素（一个更小，一个更大）。

下面是上述思路的实现。

// C++程序，打印给定数组中所有三元组，
// 它们形成等差数列
#include <bits/stdc++.h>
using namespace std;
   
// 在给定的排序数组中打印所有三元组
// 形成等差数列的元素
void printAllAPTriplets(int arr[], int n)
{
    for (int i = 1; i < n - 1; i++) 
    {
   
        // 搜索形成AP的另外两个元素，arr [i] 为中间元素。
        for (int j = i - 1, k = i + 1; j >= 0 && k < n;) 
        {
   
            // 如果找到一个三元组
            if (arr[j] + arr[k] == 2 * arr[i]) 
            {
                cout << arr[j] << " " << arr[i]
                     << " " << arr[k] << endl;
   
                // 因为元素是不同的，
                // arr [k] 和 arr [j] 不能再与 arr [i] 形成三元组
                k++;
                j--;
            }
   
            // 如果中间元素更大，则向上移动，否则向下移动。
            else if (arr[j] + arr[k] < 2 * arr[i]) 
                k++;         
            else
                j--;         
        }
    }
}
   
// 主函数
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;
}  

输出：

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(1)