与给定数字最接近的三元组和

问题陈述

给定一个由 N 个整数组成的整数数组 arr[] 和一个整数 X，目标是找出 arr[] 中的三个整数，它们的和最接近 X。

示例测试用例

测试用例 1

输入: arr[] = {-3, 5, 2, -8, 10}, X = 7

输出 7

说明

三元组的和

(-3) + 5 + 2 = 4

5 + 2 + (-8) = -1

(-3) + 2 + (-8) = -9

4 最接近 7。

测试用例 2

输入: arr[] = {0, -6, 4, 9, -2}, X = 3

输出 1

说明

三元组的和

0 + (-6) + 4 = -2

(-6) + 4 + 9 = 7

0 + 4 + (-2) = 2

1 最接近 3。

测试用例 3

输入: arr[] = {7, -1, 3, 6, -4}, X = 2

输出 0

说明

三元组的和

7 + (-1) + 3 = 9

(-1) + 3 + 6 = 8

7 + 3 + (-4) = 6

0 最接近 2。

方法 1：朴素方法

一种直接的方法是穷举检查给定数组中的所有大小为三的子集。在此过程中，算法会记录目标值 X 与每个子集和之间的差值。然后，找出其和与 X 之间差值最小的子集，并将其作为结果返回。

算法

1. 使用带有计数器 i、j 和 k 的三个嵌套循环来实现解决方案。
2. 第一个循环从头开始迭代到尾，第二个循环从 i+1 迭代到尾，第三个循环从 j+1 迭代到尾。
3. 在循环中，评估位置 i、j 和 k 处元素的和与给定目标和之间的差值是否小于当前最小差值。

如果是，则更新当前最小值。最后，输出获得的最近和。

上述方法的 Java 实现

输出

复杂度分析

时间复杂度: O(n^3)

• 对于三个 for 循环的迭代

空间复杂度： O(1)

• 由于没有额外的空间使用，空间复杂度保持不变

方法 2：使用排序

• 通过在排序数组后使用双指针技术来提高算法的效率。
• 优化方法涉及遍历数组并查找三元组的第一个元素。
• 随后，应用双指针算法来查找最接近 (x - array[i]) 的数字。然后相应地更新最接近的和。

使用双指针算法可实现线性时间复杂度，使其成为嵌套循环的更好替代方案。

算法

1. 将提供的数组按升序排列。
2. 遍历数组，将 arr[i] 指定为潜在三元组的固定第一个元素。
3. 随后，设置两个指针，一个指向 i + 1，另一个指向 n - 1，其中 n 是数组的大小。评估由 arr[i]、arr[left] 和 arr[right] 组成的三元组的和。
4. 如果和小于目标和，则增加左指针。
5. 相反，如果和更大，则减小右指针以减小和。
6. 在此过程中，持续更新迄今为止遇到的最接近的和。

上述方法的 Java 实现

输出

复杂度分析

时间复杂度：O(n^2)

空间复杂度： O(1)