内容来自互联网，做了一定修改
方法1：
这个问题和求子数组最大值优点相似，但解法不同，如果按照求子数组最大值的方法来求解，我们可以求出以j为截止的最大值和最小值，如果最大值和最小值都>0,那么最小值即为所求，如果都<0，那么最大值就为所求，如果有一个值为0，那么为0的就为所求，但问题是如果最大值>0而最小值<0的情况，需要向前回溯才能解决。因此复杂度还是N^2。所以这里不能够采用与求解数组中和最大的子数组相同的方式求解。
方法2：
我们可以尝试使用“将x[0...n-1]扩展为x[0...n]”的思想，建立一个累积和表cumSum进行处理。这里假设输入数组为x[n]，那么则有
由此我们发现，cumSum两个元素的差值恰好对应一个子数组的和。
剩下我们只需要对cumSum进行排序，然后寻找最接近（差值的绝对值最小）的相邻的两个数即可。在cumSum和数组中最接近的相邻两个数表示的就是原来数组x中两个最接近的子数组的和。然后这两个子数组之间的隔着的数的和就是最接近于0的子数组的和。因为两个子数组之间隔着的数的和就是上面cumSum中两个最接近的相邻两个数的差。
一定注意有一个非常容易出错的地方：
观察公式可以发现，由于cumSum[l-1]需是一个有效值，那么l必须大于等于1，而两个cumSum元素做差得到的子数组至少都是从原数组x的第二个元素开始。也就是说无法包括从第一个元素就开始的情况。从第一个数组开始的情况对应的就是cumSum中不是两个数的差值最小，而是cumsum中某个数的值最小。所以必须在cumsum中增加一位，应对这种自身就是最小的情况。一个好办法就是增加一个cumsum[0]=0，自身减去0还是自身。
如果题目要求的最接近于0的子数组恰好包含x中的第一个元素，那么这个方法将会得到不正确的结果，比如对于这个经过特别构造的输入：
-5，2，2，3，2
算法得不到正确的结果。因为此时不增加0的话cumsum=[-5，-3，-1,2,4]；求出最接近0的和是-2.明显错误。增加0之后：cumsum=[-5，-3，-1，0,2,4]；求出最接近0的和是-1，正确。
所以我们有必要对原来的算法做一点调整，调整的方式很简单，我们只需要将cumSum的元素往后挪一个位置即可，即
因为首元素t要参与排序和做差，而引入这个元素不能影响其他元素，所以t只能取0
ps：其实这个调整还可以这么理解。由于cumSum中保存的本身就是部分子数组的和，且这个和始终包含第一个元素。而原来算法所得到的子数组之和是从第二元素开始计算，所以他丢掉了检测cumSum元素自身的情况。而和0做差的结果就是自身。
因为首先要对cumsum进行排序，用快速排序对于cumsum进行排序在O(nlogn)时间内完成。所以问题本身的理论下界是O(nlogn)。采用这种方法得到的运行时间不超过最优时间的常数倍。
具体程序：
#include<iostream>
using namespace std;
bool InputIsInvalid=false;
int comp(const void* a,const void* b)//主要是用在qsort函数中的比较规则,且注意这里一定要是const指针
{
return *(int*)a-*(int*)b;
}
int abs(int a)
{
return a>0?a:(-1*a);
}
int Min(int a,int b)
{
return a>b?b:a;
}
int Near0SumInArray(int a[],int length)
{
if(a==NULL||length<=0)
{
InputIsInvalid=true;
return -1;
}
int *cursum=new int [length+1];
cursum[0]=0;//处理特殊情况
for(int i=0;i<length;i++)
cursum[i+1]=cursum[i]+a[i];
qsort(cursum,length+1,sizeof(int),comp);
int min=cursum[1]-cursum[0];
for(int j=2;j<length+1;j++)
{
int temp=cursum[j]-cursum[j-1];
if(abs(temp)<abs(min))//注意这里比较的是绝对值大小
min=temp;//排序后，会打乱原有的元素和排列顺序，要分辨真实的正负号.这里为了简便就没有讨论这个min的正负号
}
return min;
}
int main()
{
int a[]= {-5,2,2,3,2};
int length=sizeof(a)/sizeof(length);
int result=Near0SumInArray(a,length);
cout<<result<<endl;
}
如果要具体输出这个最接近于0的子数组的话 定义一个结构体，一个记录位置i,一个记录和sum。具体程序如下所示：
#include<iostream>
using namespace std;
bool InputIsInvalid=false;
struct data
{
int value;
int index;
};
int comp(const void* a,const void* b)//主要是用在qsort函数中的比较规则,且注意这里一定要是const指针
{
return (*(data*)a).value>(*(data*)b).value;//qsort中数按照升序排序,而且是结构体的升序排序
}
int abs(int a)
{
return a>0?a:(-1*a);
}
void Near0SumInArray(int a[],int length)
{
if(a==NULL||length<=0)
{
InputIsInvalid=true;
return;
}
data *cursum=new data[length+1];
cursum[0].index=-1;//注意这里增加的那个数要把它的标号设置为-1
cursum[0].value=0;
for(int i=0;i<length;i++)
{
cursum[i+1].value=cursum[i].value+a[i];
cursum[i+1].index=i;
}
qsort(cursum,length,sizeof(cursum[0]),comp);//按照升序排序
int min=65535;
int startindex=0;
int endindex=0;
for(int i=1;i<length+1;i++)
{
int temp=cursum[i].value-cursum[i-1].value;
if(abs(temp)<abs(min))
{
min=temp;
if(cursum[i-1].index>cursum[i].index)//注意因为对cursum进行从新排序了，所以序号不再是按照对应顺序的
{
startindex=cursum[i].index+1;//之前cursum[i]表示的是前i-1个的和，排序后就不具有这个性质了，所以要讨论start和end位置
endindex=cursum[i-1].index;
}
else
{
startindex=cursum[i-1].index+1;//注意这里对于起始标号需要加1
endindex=cursum[i].index;
}
}
}
int result=0;
for(int i=startindex;i<=endindex;i++)
{
cout<<a[i]<<" ";
result+=a[i];//因为之前求出min的正负号无法判断，所以这里必须对找到的数再求一次和，才能够确认它的正负号
}
cout<<endl;
cout<<"Near0Sum= "<<result<<endl;
}
int main()
{
int a[]= {-5,2,2,3,2};
int length=sizeof(a)/sizeof(length);
Near0SumInArray(a,length);
return 0;
}
以上在编写代码的时候要注意利用qsort函数的时候comp排序规则的定义，尤其是结构体排序规则的定义。其次就是在求解时一定要注意解的正负号。