算法题（总和最接近K的子数组） _总和最接近K的子数组

给定正负整数数组和整数K。任务是找到总和最接近k的子数组。如果有多个答案, 请打印任何一个。
注意：
这里最接近意味着abs(sum-k)应该最小。
例子：

输入：a [] = {-5, 12, -3, 4, -15, 6, 1}, K = 2
输出：1子数组{-3, 4}或{1}的总和= 1, 即
输入：a [] = {2, 2, -1, 5, -3, -2}, K = 7
输出：6
这里的输出可以是6或8
子数组{2, 2, -1 , 5}得出总和为8, 其abs(8-7)= 1, 与具有abs(6-7)= 1的子数组{2, -1, 5}的总和相同。

一种天真的方法是使用前缀和检查所有可能的子数组和。在这种情况下, 复杂度将为O(N2)。
An有效的解决方案将使用C++++ STL集和二进制搜索解决以下问题。请按照以下算法解决以上问题。

首先将第一个元素插入集合容器中。
初始化答案和作为第一要素区别作为abs(A0-k)。
迭代从1到N的所有数组元素, 并继续在每个步骤中将元素添加为前缀sum到集合容器中。
在每次迭代中, 由于前缀和已经存在, 所以我们只需要从开始就减去一些元素的和即可得到任何子数组的和。贪婪的方式将是减去子数组的和, 该子数组的和最接近K。
使用二进制搜索(lower_bound()可以使用函数)从开头开始找到最接近(prefix-k)的子数组之和, 因为从前缀和减去该数字将得到直到迭代为止最接近K的子数组之和。
此外, 还要检查是否有返回lower_bound()的索引, 因为总和可以大于或小于K。
如果lower_bound不返回任何此类元素, 那么将比较当前前缀和, 如果其小于先前计算的和, 则更新当前前缀。

下面是上述方法的实现。

//C++ program to find the //sum of subarray whose sum is //closest to K #include < bits/stdc++.h> using namespace std; //Function to find the sum of subarray //whose sum is closest to K int closestSubarraySumToK( int a[], int n, int k) {//Declare a set set< int> s; //initially consider the //first subarray as the first //element in the array int presum = a[0]; //insert s.insert(a[0]); //Initially let this difference //be the minimum int mini = abs (a[0] - k); //let this be the sum //of the subarray //to be searched initially int sum = presum; //iterate for all the array elements for ( int i = 1; i < n; i++) {//calculate the prefix sum presum += a[i]; //find the closest subarray //sum to by using lower_bound auto it = s.lower_bound(presum - k); //if it is the first element //in the set if (it == s.begin()) {//get the prefix sum till start //of the subarray int diff = *it; //if the subarray sum is closest to K //than the previous one if ( abs ((presum - diff) - k) < mini) {//update the minimal difference mini = abs ((presum - diff) - k); //update the sum sum = presum - diff; } }//if the difference is //present in between else if (it != s.end()) {//get the prefix sum till start //of the subarray int diff = *it; //if the subarray sum is closest to K //than the previous one if ( abs ((presum - diff) - k) < mini) {//update the minimal difference mini = abs ((presum - diff) - k); //update the sum sum = presum - diff; }//also check for the one before that //since the sum can be greater than //or less than K also it--; //get the prefix sum till start //of the subarray diff = *it; //if the subarray sum is closest to K //than the previous one if ( abs ((presum - diff) - k) < mini) {//update the minimal difference mini = abs ((presum - diff) - k); //update the sum sum = presum - diff; } }//if there exists no such prefix sum //then the current prefix sum is //checked and updated else {//if the subarray sum is closest to K //than the previous one if ( abs (presum - k) < mini) {//update the minimal difference mini = abs (presum - k); //update the sum sum = presum; } }//insert the current prefix sum s.insert(presum); }return sum; }//Driver Code int main() { int a[] = { -5, 12, -3, 4, -15, 6, 1 }; int n = sizeof (a) /sizeof (a[0]); int k = 2; cout < < closestSubarraySumToK(a, n, k); return 0; }

【算法题（总和最接近K的子数组）】时间复杂度：O(N对数N)