C++程序查找和为给定值的三元组

给定一个数组和一个值，在数组中查找是否存在三元组的和等于给定值。如果存在这样的三元组，输出该三元组并返回True，否则返回False。

例子:

输入: array = {12, 3, 4, 1, 6, 9}, sum = 24;

输出: 12, 3, 9

解释: 序列中包含三元组(12，3和9)使得它们的和为24.

输入: array = {1, 2, 3, 4, 5}, sum = 9

输出: 5, 3, 1

解释: 序列中包含三元组(5，3和1)使得它们的和为9.

方法1： 这是对解决上述问题的一种朴素方法。

方法： 一个简单的方法是生成所有可能的三元组，并将每个三元组的和与给定值进行比较。以下代码使用三个嵌套循环实现了这种简单的方法。
算法：
1. 给定长度为n的数组和一个值s
2. 创建三个嵌套循环，第一个循环从开始到结尾(循环计数器为i)，第二个循环从i+1循环到结尾(循环计数器为j)，第三个循环从j+1循环到结尾(循环计数器为k)。
3. 这些循环的计数器表示三元组的3个元素的索引。
4. 查找第ith、jth和kth元素的总和。如果总和等于给定的和，则输出该三元组并且退出。
5. 如果没有三元组，则输出没有三元组存在。
实现:

#include <bits/stdc++.h>
using namespace std;
  
// 返回true 如果存在和为sum的三元组在A[]中. 同时输出该三元组
bool find3Numbers(int A[], int arr_size, int sum) 
{ 
    int l, r; 
  
    // 将第一个元素固定为A[i]
    for (int i = 0; i < arr_size - 2; i++) { 
  
        // 将第二个固定为A[j]
        for (int j = i + 1; j < arr_size - 1; j++) { 

            // 查找第三个数
            for (int k = j + 1; k < arr_size; k++) { 

                if (A[i] + A[j] + A[k] == sum) { 
                    cout << "Triplet is " << A[i] << ", " 
                        << A[j] << ", " << A[k]; 
                    return true; 
                } 
            } 
        } 
    } 
  
    // 如果执行到这里，证明不存在三元组
   return false; 
} 
  
/* 主函数 */
int main() 
{ 
    int A[] = { 1, 4, 45, 6, 10, 8 }; 
    int sum = 22; 
    int arr_size = sizeof(A) / sizeof(A[0]); 
    find3Numbers(A, arr_size, sum); 
    return 0; 
} 
  
// 本代码由rathbhupendra贡献```

输出

Triplet is 4, 10, 8

时间复杂度和空间复杂度分析：
- 时间复杂度: O(n 3 ). 由于有三层嵌套循环遍历数组，因此时间复杂度是O(n^3)。
- 空间复杂度: O(1). 由于不需要额外的空间。

方法2: 这种方法使用排序来增加代码的效率。

方法： 通过对数组进行排序，可以提高算法的效率。这种高效的方法使用了双指针技术。遍历数组，并固定三元组的第一个元素。现在使用双指针算法来查找是否有一对元素的和等于 x – array[i]。双指针算法需要线性时间，因此比嵌套循环好。
算法：
1. 对给定数组进行排序。
2. 循环遍历数组，并固定可能的三元组的第一个元素 arr[i]。
3. 然后固定两个指针，一个指向 i + 1，另一个指向 n – 1。查看它们的和，
  1. 如果和小于所需的和，则增加第一个指针。
  2. 否则，如果和大，减小末尾指针以减少和。
  3. 否则，如果两个指针的元素之和等于给定的和，则打印三元组并退出。
实现：

// C++ program to find a triplet
#include <bits/stdc++.h>
using namespace std;
  
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;
  
    /* Sort the elements */
    sort(A, A + arr_size);
  
    /* Now fix the first element one by one and find the
       other two elements */
    for (int i = 0; i < arr_size - 2; i++) {
  
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
        // remaining elements
  
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) {
                printf("Triplet is %d, %d, %d", A[i],
                       A[l], A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
  
    // If we reach here, then no triplet was found
    return false;
}
  
/* Driver program to test above function */
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);
  
    find3Numbers(A, arr_size, sum);
  
    return 0;
}

输出

Triplet is 4, 8, 10

复杂度分析：
- 时间复杂度： O(N^2)。只有两个嵌套循环遍历数组，因此时间复杂度为 O(n^2)。双指针算法需要 O(n) 的时间，而第一个元素可以使用另一个嵌套遍历固定。
- 空间复杂度： O(1)。不需要额外的空间。

方法 3： 这是一种基于哈希的解决方案。

方法： 此方法使用额外的空间，但比双指针方法更简单。外部循环从开头到结尾，内部循环从 i+1 到结尾。创建一个哈希表或集合来存储 i+1 到 j-1 之间的元素。因此，如果给定的和为 x，则检查集合中是否有一个数字等于 x – arr[i] – arr[j]。如果是，就打印三元组。
算法：
1. 从开始到结尾遍历数组（循环计数器 i）。
2. 创建哈希表或集合以存储唯一的对。
3. 从 i+1 到数组结尾运行另一个循环（循环计数器 j）。
4. 如果集合中有一个元素等于 x – arr[i] – arr[j]，则打印三元组（arr[i]，arr[j]，x-arr[i]-arr[j]）并退出。
5. 将第 j 个元素插入集合中。
实现：

// C++ 程序，使用哈希表查找三元组
#include <bits/stdc++.h>
using namespace std;

// 如果 A[] 中存在和为 sum 的三元组，则返回 true。并且打印这个三元组
bool find3Numbers(int A[], int arr_size, int sum)
{
    // 将 A[i] 作为第一个元素
    for (int i = 0; i < arr_size - 2; i++) 
    {

        // 在子数组 A[i+1..n-1] 中查找和为 sum - A[i] 的一对
        unordered_set<int> s;
        int curr_sum = sum - A[i];
        for (int j = i + 1; j < arr_size; j++) 
        {
            if (s.find(curr_sum - A[j]) != s.end()) 
            {
                printf("三元组是 %d, %d, %d", A[i], A[j], curr_sum - A[j]);
                return true;
            }
            s.insert(A[j]);
        }
    }

    // 如果没有找到三元组则返回 false
    return false;
}

// 主程序，用于测试以上函数
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);

    find3Numbers(A, arr_size, sum);

    return 0;
}