C++ 4Sum - 查找和最接近的四元组

4 Sum（查找和最接近的四元组）问题属于 k-Sum 问题类别，这些问题都与查找一组数字，使其总和等于目标值或接近目标值有关。在这里，问题是确定数组中的四个数字（一个四元组），它们的总和尽可能接近给定的特定数字。

为了解决这个问题，通常会实现有用的排序算法，例如排序和双指针方法，以降低时间复杂度。当数组被排序后，可以使用两个循环固定前两个数字，然后可以使用双指针技术轻松固定另外两个数字，最终使问题的复杂度等于 O(n^3)。排序后的数组有助于结构化地搜索组合，而双指针可用于根据当前四元组的总和来控制搜索过程，以查找接近目标总和的值。

目标是在优化总和的过程中，尽可能地接近目标。每当获得一个更接近目标的四元组总和时，它就会替换之前找到的。一旦找到等于目标的精确值，搜索就可以停止，因为不会有更好的解决方案。

这个问题是优化排序和双指针等技术以及在最高效的语言中实现解决方案的又一个好例子。这个问题还表明，在处理大型数据集时，应采用适当的数据结构和算法，而不会冒性能低下的风险。

方法一：暴力破解法

暴力破解方法在解决 4 Sum 问题时可能很容易实现，但效率极低。在此方法中，会检查输入数组中任意 4 个元素相加的所有可能性，以找到最接近给定目标的正确组合。

程序

让我们以一个示例说明使用 C++ 中的暴力破解法来解决 4 sum 问题。

输出

 
Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1   

说明

• 在此示例中，<vector> 头文件允许使用 动态数组 类型 std::type，或者需要一个 vector，这对于处理数字集至关重要。
• 它提供了有用的宏，例如 INT_MAX，可用于将保存所查找项的变量设置为一个极大的值，并以此进行比较。它包含基本的数学运算，如 abs()，用于查找绝对差。

函数 fourSumClosest

• 此函数有两个输入参数：nums，一个整数向量；target，一个表示最接近总和的整数。该函数返回最接近目标的任何四元组。
• 该函数首先执行一个if 语句来确定输入向量的大小是否小于四个。如果是，它将打印错误消息并且不会继续执行，因为不可能用少于四个元素构成一个四元组。
• 赋给 adjacent sum closestSum 的值是 Int 类型的最大值 INT_MAX，以确保在迭代期间遇到的任何计算出的四元组总和都可以覆盖此初始值。

嵌套循环

• 暴力破解方法的核心是四个 嵌套循环，它们生成输入向量中所有可能的四个不同元素组合。
• 外层循环选择第一个数字，第二个循环选择第二个数字。每个循环之后，下一个循环从选定数字的索引值开始，以避免重复相同的值并大大增加列表之间的差异。
• 对于这些组合中的每一种，都会计算随机选择的四个数字的总和。

最接近的总和计算

• 在将四元组的当前总和计算出来并将其标记为最接近目标之前，该 函数会将其与之前的最接近总和进行比较。如果当前总和更接近，则使用 abs() 函数计算总和以获得绝对差。如果当前总和更接近，它将更新 closestSum。

输入显示函数

• 当使用该包时，此函数会打印输入向量和目标总和。在测试期间，这有助于解释输入数据。

测试函数

• C++ 文件链接还显示了 testFourSumClosest，其中包含带有数组输入和目标总和的多个测试用例。对于每个用例，它都会调用 fourSumClosest 并打印结果，从而大大简化了函数验证。

复杂度分析

时间复杂度

此暴力破解方法的时间复杂度确定为 O(n^4)。此复杂度源于用于遍历数组的四个嵌套循环。

• 外层循环：第一个循环从列表的第一个索引运行到倒数第四个索引。
• 第二个循环：第二个循环从第一个元素的下一个元素开始，移动到倒数第三个元素。
• 第三个循环：第三个循环从第二个循环索引之后开始，结束于倒数第二个元素。
• 最内层循环：最内层循环从第三个循环的索引之后开始，一直运行到数组的最后一个元素。

在这方面，由于每个循环都依赖于其他循环，因此正在评估的组合数量是输入数组大小的多项式，特别是四阶多项式。因此，迭代次数随着输入大小的增加而增加，这对于大型数据集来说是一个关键问题，并且会严重降低执行速度。

空间复杂度

此方法的空间复杂度为常数 O(1)。这意味着算法除了输入数组所需的空间外，还需要恒定的额外空间。indices_alloc、current_sum 和 best_sum 变量用于存储索引、当前总和和最佳总和，并且这些变量不会随着输入大小的增加而增加。因此，该算法不需要与输入大小成比例的空间复杂度的辅助数据结构，因此内存效率很高。

方法二：排序和双指针技术

优化并选择双指针方法是 4 Sum（查找和最接近的四元组）问题的良好解决方案。与上述使用暴力破解排序方法和双指针方法相比，此方法将时间复杂度降低了一半。

程序

让我们以一个示例说明使用 C++ 中的排序和双指针技术来解决 4 sum 问题。

输出

 
Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1   

说明

• 主函数 fourSumClosest 接受一个整数向量 Indeed，其中包含一些整数和一个整数 target 作为参数。首先，它验证数组的大小是否小于四个，如果是，则返回错误。
• 在对数组进行排序以使用双指针技术后，该函数使用两个循环来调整四元组的前两个组成部分。对于每个固定的对，两个指针（left 和 right）被设置为其余两个数字的潜在候选。
• 计算所选四个数字的总和，然后与目标总和进行比较。此外，displayInput 函数打印输入数组和目标，以便在测试期间更加清晰。testFourSumClosest 函数考虑多个测试场景，调用 fourSumClosest 并显示其结果。
• 因此，该方法在时间复杂度方面取得了良好改进，稳定在 O(n^3)，优于大型数据集的暴力破解方法。总的来说，代码结构允许进行结构化测试，即使在适用各种情况和细微差别时也能获得高度可靠的结果。同时，代码具有高度的词法一致性，没有混合功能。

复杂度分析

时间复杂度

• 在 4 Sum-查找和最接近的四元组问题中使用的技术，即排序和双指针技术，其时间复杂度为 (O(n3))。这是因为对给定输入数组进行排序以及用于识别对的嵌套循环是复杂的。
• 因此，排序操作的顺序为 (O(n logn))。第一个遍历数组的循环对时间贡献为 (O N2)，第二个遍历数组的循环也对时间贡献为 (O (n2)。
• 最内层循环与双指针技术结合仍然需要时间来处理其余元素，使得整个函数平均为 (O(n3))。因此，该算法有效地减少了搜索空间，这使其适用于大型输入大小，优于暴力破解方法。

空间复杂度

• 此方法的空间复杂度为 (O(1))，算法仅消耗恒定的额外空间。唯一使用的其他存储是用于索引、总和和最近发现的总和的几个整数 变量。输入数组是就地排序的，除了输入数组本身之外，不使用任何其他数据结构，这些数据结构的大小与输入大小成正比。这种时间和空间效率实际上使排序和双指针技术在 4 Sum 问题中很有用。