极客教程C++程序 查找三元组，使得两个元素的和等于第三个元素
给出一个整数数组，您需要找到三个数字，使得两个元素的和等于第三个元素。
示例：
输入： {5, 32, 1, 7, 10, 50, 19, 21, 2}
输出： 21, 2, 19
输入： {5, 32, 1, 7, 10, 50, 19, 21, 0}
输出： 无此三元组
简单的方法： 运行三个循环并检查是否存在这样一个三元组：两个元素的和等于第三个元素。
时间复杂度 ：O(n ^ 3)
高效方法： 这个想法类似于“查找和为给定值的三元组”。
- 先对给定的数组进行排序。
- 从后面开始固定三个元素中最大的元素，遍历数组以找到另外两个元素，这两个元素的和等于第三个元素。
- 取两个指针j（从前面开始）和k（最初为i – 1）以找出其中较小的数字，并从 i-1 找到剩下两个数字中最大的数字
- 如果两个数字的加法仍然小于 A[i]，则需要增加两数之和的值，从而增加j指针，以增加 A[j]+A[k] 的值。
- 如果两个数字的总和大于 A[i]，则需要减少两数之和的值，因此减少k指针以降低 A[j]+A[k] 的总值。
下面的图是上述方法的干运行：
下面是上述方法的实现：
// C ++程序查找三个数字
//使两个元素的和等于数组中的第三个元素
#include <bits/stdc++.h>
using namespace std;
//查找数组中的三元组的实用函数
void findTriplet(int arr[], int n)
{
//对数组进行排序
sort(arr，arr+n)；
//对于arr中的每个元素，检查
//是否存在一对（在数组中）的和与arr元素相等
for (int i = n - 1; i >= 0; i--)
{
int j = 0;
int k = i - 1;
//向前向后迭代以查找其他两个元素
while (j < k)
{
//如果两个元素的和为第三个元素
if (arr[i] == arr[j] + arr[k])
{
//找到一对
cout << "numbers are " << arr[i] <<
" " << arr[j] << " " <<
arr[k] << endl;
return;
}
//如果该元素大于两个元素的和，则尝试
//添加更小的数字以达到平等
else if(arr[i] > arr[j] + arr[k])
j += 1;
//如果该元素较小，则
//尝试使用较小的数字
//以达到平等，因此减小K
else
k -= 1;
}
}
//数组中找不到这样的三元组
cout << "找不到这样的三元组";
}
//驱动代码
int main()
{
int arr[] = {5, 32, 1, 7, 10,
50, 19, 21, 2};
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n);
return 0;
}
import java.util.Arrays;
public class Triplet {
// 在数组中找到三元组的实用函数
public static void findTriplet(int[] arr, int n)
{
// 对数组进行排序
Arrays.sort(arr);
// 对于数组中的每个元素检查
// 是否存在一对(在数组中)其和等于第三个元素
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
// 向前和向后迭代以查找另外两个元素
while (j < k) {
// 如果两个元素的和等于第三个元素
if (arr[i] == arr[j] + arr[k]) {
// 找到一对
System.out.println(
"numbers are " + arr[i] + " "
+ arr[j] + " " + arr[k]);
return;
}
// 如果元素大于两个元素的和，则尝试
// 添加一个较小的数达到相等
else if (arr[i] > arr[j] + arr[k]) {
j += 1;
}
// 如果元素较小，则尝试
// 用一个更小的数字打到相等，所以减小k
else {
k -= 1;
}
}
}
// 在数组中没有找到这样的三元组
System.out.println("No such triplet exists");
}
public static void main(String[] args)
{
int[] arr = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = arr.length;
findTriplet(arr, n);
}
}
输出：
numbers are 21 2 19
时间复杂度 ：O(N^2)
辅助空间：O(1)
另一种方法： 思路类似于前面的方法。
- 对给定的数组进行排序。
- 开始一个嵌套循环，固定第一个元素i(从0到n-1)，移动另一个元素j(从i+1到n-1)。
- 对这两个元素的和进行求和，并在剩余的数组中搜索它，使用 二进制搜索。
// C++程序：查找三个数
// 使得其中两个数的和等于数组中的第三个数
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// 二分查找函数
bool search(int sum, int start,
int end, int arr[])
{
while (start <= end)
{
int mid = (start + end) / 2;
if (arr[mid] == sum)
{
return true;
}
else if (arr[mid] > sum)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return false;
}
// 查找三元组的函数
void findTriplet(int arr[], int n)
{
// 对数组进行排序
sort(arr, arr + n);
// 初始化嵌套循环
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// 计算两数之和
if (search((arr[i] + arr[j]),
j, n - 1, arr))
{
// 输出第一个三元组
cout << "Numbers are: " << arr[i] <<
" " << arr[j] << " " <<
(arr[i] + arr[j]);
return;
}
}
}
// 如果没有这样的三元组
cout << "No such numbers exist" << endl;
}
// 主函数
int main()
{
int arr[] = {5, 32, 1, 7, 10,
50, 19, 21, 2};
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n);
return 0;
}
// 此代码由Sarthak Delori贡献
import java.util.Arrays;
// 查找三个数使得其中两个数的和等于数组中的第三个数的类
public class TripletSum {
// 二分查找函数
public static boolean search(int sum, int start,
int end, int arr[])
{
// 执行二分查找
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == sum) {
// 如果查找的和在数组中找到，则返回true
return true;
}
else if (arr[mid] > sum) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
// 如果查找的和没有在数组中找到，则返回false
return false;
}
// 函数查找三元组
public static void findTriplet(int arr[], int n)
{
// 对数组进行排序
Arrays.sort(arr);
// 初始化嵌套循环
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 计算两数之和
if (search((arr[i] + arr[j]), j, n - 1,
arr)) {
// 输出第一个三元组
System.out.println(
"Numbers are: " + arr[i] + " "
+arr[j] + " " + (arr[i] + arr[j]));
return;
}
}
}
// 如果没有这样的三元组
System.out.println("No such numbers exist");
}
// 主函数
public static void main(String[] args)
{
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = arr.length;
findTriplet(arr, n);
}
}
时间复杂度： O(N^2*log N)
空间复杂度： O(1)