算法题：总和最接近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;
}

时间复杂度：O(N对数N)

---