我最近在算法课上有一个作业。问题陈述如下：
写一下并简要解释下面的C ++函数：
int Sum (int *nums, int len);接受一个整数数组，nums，包含len> 0正整数，并返回最接近330的和，它是通过在数组中加起来最多三个整数找到的（其中每个元素都是数组只能包含在总和中一次）。例如，如果[nums]包含[10 100 200 2]且len == 4，则函数返回310 = 200 + 100 + 10。如果[nums]包含[10 100 230 2]且len == 4，则函数返回330 = 100 + 230。
我对代码的尝试：
#include <iostream>
#include <limits.h>
#include <cmath>
#include <climits>
using namespace std;
/*
* Description: function to find the sum closed to 330 by adding up
* to 3 integers
* Arguments : nums - integer array
* len - length of integer array
* Return : sum closest to 330
*/
int Sum (int *nums, int len)
{
const int number = 330;
/* variable to store sum closest to 330 */
int closest_sum = 0;
/* variable to store difference of sum from 330 */
int diff = INT_MAX;
/* iterate over the integer array to find the sum closest to 330 */
for(int i = 0; i < len; i++)
{
/* temporary variable to hold sum of integers */
int sum = 0;
/* set first of 3 numbers as the sum */
sum = nums[i];
/* if the first number is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with previous */
/* difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous difference, */
/* update diff and set closest sum to current sum */
diff = abs(number - sum);
closest_sum = sum;
}
/* include the second of 3 numbers */
for(int j = i + 1; j < len; j++)
{
/* set sum as the addition of the first 2 numbers */
sum = nums[i] + nums[j];
/* if the sum is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with previous */
/* difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous difference, */
/* update diff and set closest sum to current sum */
diff = abs(number - sum);
closest_sum = sum;
}
/* include the third of 3 numbers */
for(int k = j + 1; k < len; k++)
{
/* set sum as the addition of the 3 numbers */
sum = nums[i] + nums[j] + nums[k];
/* if the sum is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with */
/* previous difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous */
/* difference, update diff and set closest sum to current */
/* sum */
diff = abs(number - sum);
closest_sum = sum;
}
}
}
}
/* return closest sum to 330 */
return closest_sum;
}
int main() {
const int len = 6;
int arr[len] = {300, 320, 310, 500, 5, 330};
cout << "Closest to 330:\t" << Sum(arr, len) << endl;
return 0;
}
代码正常工作并传递了分级器使用的所有测试用例。但是，部分标记与代码的效率有关。我失去了分数，因为代码的运行时间是Θ（n ^ 3）（因为三个嵌套的for循环）。
我的问题是：如何将此算法提高到更高效，即运行时间小于Θ（n ^ 3）？
编辑：只是为了说清楚，直到这个任务到期的时候，我们只研究了数组/向量，渐近符号，类中的递归/重现时间。我很确定我们不会使用堆，二进制搜索（事实上，我们将在下周研究），排序算法等。另外，请注意问题说最多三个整数，即最接近的总和330可以由1个数字，2个数字或3个数字组成。我必须考虑到所有这些可能性。
如果您首先对数字进行排序，则可以使用嵌套循环来测试每对数字，并使用二进制搜索选择第三个数字。
该算法的复杂度为O（N ^ 2 * log（N）），（加上N log（N）进行排序）
我怀疑你的导师可能会想到一个错误的答案。
您可以使用两个循环生成所有对总和的向量，然后使用另外两个循环向这些循环添加第三个数字。这“避免”第三级嵌套。
然而，这个答案是错误的，因为生成的矢量的长度是O（N ^ 2）。这为O（N ^ 2）循环内部提供了一个O（N）循环，使得两个循环的复杂性结合起来O（N ^ 3）
这里你的问题的根本原因是确实有N ^ 3个可能的总和。即使你考虑到3！您可以添加三个数字的不同顺序，任何考虑所有可能的三元组的解决方案必须是O（N ^ 3）。任何更好的解决方案都必须完全省略一些金额。 Sebastia'n现有的答案通过对输入进行排序来跳过这些总和中的一些，因此您可以通过日志（N）二进制搜索消除大量可能性。但只有一个简单的常规向量，你不能跳过任何输入。
有一些技巧可以改善预期的运行时间，但只有一个常量。例如，您可以在O（N）中计算输入的最小值和最大值。然后，您可以通过从所有输入中减去最小值来简化问题，并从目标值中减去3 *。即问题[10 100 200 2] => 330简化为[8 98 198 0] = > 324。拥有最大值的优点是您可以跳过某些对的内循环。添加8+0之后，很明显即使添加最大的198也只能达到206，这将比您在此时获得的最佳结果更差。