极客教程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： 这是对解决上述问题的一种朴素方法。
- 方法： 一个简单的方法是生成所有可能的三元组，并将每个三元组的和与给定值进行比较。以下代码使用三个嵌套循环实现了这种简单的方法。
- 算法：
- 给定长度为n的数组和一个值s
- 创建三个嵌套循环，第一个循环从开始到结尾(循环计数器为i)，第二个循环从i+1循环到结尾(循环计数器为j)，第三个循环从j+1循环到结尾(循环计数器为k)。
- 这些循环的计数器表示三元组的3个元素的索引。
- 查找第ith、jth和kth元素的总和。如果总和等于给定的和，则输出该三元组并且退出。
- 如果没有三元组，则输出没有三元组存在。
- 实现:
#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]。双指针算法需要线性时间，因此比嵌套循环好。
- 算法：
- 对给定数组进行排序。
- 循环遍历数组，并固定可能的三元组的第一个元素 arr[i]。
- 然后固定两个指针，一个指向 i + 1，另一个指向 n – 1。查看它们的和，
- 如果和小于所需的和，则增加第一个指针。
- 否则，如果和大，减小末尾指针以减少和。
- 否则，如果两个指针的元素之和等于给定的和，则打印三元组并退出。
- 实现：
// 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]。如果是，就打印三元组。
-
算法：
- 从开始到结尾遍历数组（循环计数器 i）。
- 创建哈希表或集合以存储唯一的对。
- 从 i+1 到数组结尾运行另一个循环（循环计数器 j）。
- 如果集合中有一个元素等于 x – arr[i] – arr[j]，则打印三元组（arr[i]，arr[j]，x-arr[i]-arr[j]）并退出。
- 将第 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;
}
输出：
三元组是 4, 8, 10
时间复杂度： O(N^2)
空间复杂度： O(N)