算法-一个整型数组，正负数都有，求这个数组的一个子数组，要求和最接近0

Question

一个整型数组，正负数都有，求这个数组的一个子数组，要求和最接近0

Answer 1

这是个经典问题了。所谓经典问题就是已经有一个成套路的解法，然后大家觉得这个大约是最佳的了。
1. 首先将所有元素按绝对值从大到小排序（据信有利于剪枝）
2. 计算出最右边K个数中，所有正数的和，和所有负数的和，记作V+[K], V-[K]
3. 取最小的正数、最大的负数、两者之和中绝对值最小的一个作为剪枝边界M
4. 从左到右递归穷举或递推生成所有的解。如果当前的数值R + V+[K] < -M, 或者R + V-[K] > M，那么当前这个部分和已经没有前途了，剪枝剪掉

采用递归还是递推视问题规模。递推要快一些，占用内存也多一些。
C#代码：

int MinAbs(int[] values)
{
//按绝对值排序，语法看不懂可以不管，反正是那个意思
Array.Sort(values, (x,y)=>(Math.Abs(x) < Math.Abs(y) ? -1 : (Math.Abs(x) > Math.Abs(y) ? 1 : 0)));
int currMinAbs = Math.Abs(values[values.Length - 1]);
int[] SumNeg = new int[values.Length];
int[] SumPos = new int[values.Length];
SumNeg[0] = SumPos[0] = 0;
for(int i = 1; i < values.Length; i++)
{
int tmp = values[values.Length - i];
if(tmp < 0)
{
SumPos[i] = SumPos[i - 1];
SumNeg[i] = SumNeg[i - 1] + tmp;
}
else
{
SumPos[i] = SumPos[i - 1] + tmp;
SumNeg[i] = SumNeg[i - 1];
}
if(Math.Abs(values[values.Length - i - 1] + values[values.Length - i]) < currMinAbs)
{
currMinAbs = Math.Abs(values[values.Length - i - 1] + values[values.Length - i]);
}
}
SortedSet<int>[] allResult = new SortedSet<int>[values.Length];
allResult[0] = new SortedSet<int>();
if(values[0] + SumPos[values.Length - 1] > -currMinAbs && values[0] + SumNeg[values.Length - 1] < currMinAbs)
allResult[0].Add(values[0]);
for(int i = 1; i < values.Length; i++)
{
allResult[i] = new SortedSet<int>();
if(values[i] + SumPos[values.Length - 1 - i] > -currMinAbs && values[i] + SumNeg[values.Length - 1 - i] < currMinAbs)
{
allResult[i].Add(values[i]);
}
foreach(var v in allResult[i - 1])
{
if(values[i] + v + SumPos[values.Length - 1 - i] > -currMinAbs && values[i] + v + SumNeg[values.Length - 1 - i] < currMinAbs)
{
allResult[i].Add(values[i] + v);
if(currMinAbs > Math.Abs(values[i] + v))
{
currMinAbs = Math.Abs(values[i] + v);
}
}
}
}
return currMinAbs;
}

需要返回结果的话差别也不大

Answer 2

先计算所有的sum0-j，其中 0<= j <n，然后对sum[0-j]的数组进行排序，那么对于任何i,j段的和等于：

sum[i-j]= sum[0-j] - sum[0-i];

由于已经对sum[0-j]进行了排序，所以只要找相邻的比较就可以了，找出绝对值最接近0的sum[0-j]和sum[0-i]，那么i+1 到j 即是所求。需要特别注意的一点是，sum的最前面要增加一个初值sum[-1-0] = 0，否则，如果开始的位置从0开始时，就会出现错误。
代码如下：

 具体程序如下：

[cpp] view plaincopy
#include <stdio.h>
template<typename T>
void Swap(T& a, T& b) {
T tmp = a;
a = b;
b = tmp;
}
template<typename T>
int Partition(T array[], int start, int end) {
int j = start - 1;
T last = array[end];
for (int i = start; i < end; ++i) {
if (array[i] < last) {
Swap(array[i], array[j+1]);
j++;
}
}
Swap(array[end], array[j+1]);
return j+1;
}
template<typename T>
void QuickSort(T array[], int start, int end) {
if (start < end) {
int pivot = Partition(array, start, end);
QuickSort(array, start, pivot - 1);
QuickSort(array, pivot + 1, end);
}
}
int Abs(int a) {
return a < 0 ? -1 * a : a;
}
class SumFromStart {
public:
SumFromStart() : end_(0), sum_(0) {}
int end_;
int sum_;
bool operator<(const SumFromStart& right) {
return sum_ < right.sum_;
}
};
bool SubArraySumNearZero(int array[], int length, int* start, int* end) {
if (length < 1) {
return false;
}
if (length == 1) {
*start = 0;
*end = 0;
return true;
}
SumFromStart sum_from_start[length + 1];
sum_from_start[0].sum_ = 0;
sum_from_start[0].end_ = -1;
for (int i = 1; i <= length; ++i) {
sum_from_start[i].sum_ = sum_from_start[i-1].sum_ + array[i-1];
sum_from_start[i].end_ = i - 1;
}
QuickSort(sum_from_start, 0, length + 1);
for (int i = 0; i <= length; ++i) {
printf("%d ", sum_from_start[i].sum_);
}
printf("n");
int min = sum_from_start[1].sum_ - sum_from_start[0].sum_;
for (int i = 2; i < length; ++i) {
if (Abs(sum_from_start[i].sum_ - sum_from_start[i-1].sum_) < min) {
if (sum_from_start[i].end_ < sum_from_start[i-1].end_) {
*start = sum_from_start[i].end_ + 1;
*end = sum_from_start[i-1].end_;
} else {
*start = sum_from_start[i-1].end_ + 1;
*end = sum_from_start[i].end_;
}
}
}
return true;
}
int main(int argc, char** argv) {
int array[] = {-2, 3, 4, -5, 8, 2, -2};
int start = -1;
int end = -1;
SubArraySumNearZero(array, sizeof(array) / sizeof(int), &start, &end);
printf("%d %dn", start, end);
}

参考：http://blog.csdn.net/bertzhang/article/details/7311647
http://blog.csdn.net/kingjinzi_2008/article/details/7690194

Answer 3

如果要求的这个子数组是连续的话，那么可以用 O(n)的时间计算出。
这个问题可以转化为求连续子数组最小和的问题。即子数组之和与0之间的差距最小。
解决方法可以参考 《编程之美》中求解连续子数组最大和问题的解题思路。

int nearestToNum(int arr[],int len, int num)
{
int e = 0;
int sumAll,sumStart;
sumStart = sumAll = arr[e];
while(e < len-1)
{
e ++;
if( abs(num - arr[e]) < abs(num - (arr[e]+sumStart)) )
{
sumStart = arr[e];
}else{
sumStart += arr[e];
}
if( abs(num - sumStart)< abs(num - sumAll) )
{
sumAll = sumStart;
}
}
return sumAll;
}
int main()
{
//...
int nearestToZero = nearestToNum(arr,len,0);
return 0;
}

Answer 4

假设sum[i]=a[0]+a[1]+...+a[i];
那么任意一个子数组sum[i-j]=sum[j]-sum[i]
要和最接近0，即是|sum[i-j]|的值最小，可以通过以下算法实现：
1、求出所有的sum[i]
2、对sum数组从小到大排序
3、找出差的绝对值最小的相邻的两个sum[j]和sum[k]
4、a[j]到a[k]即是所要找的子数组

Answer 5

我想到一个思路但是还没实现，采用动态规划思想，先计算1个元素绝对值最小的，保存最小元素，再计算2个元素相加绝对值最小的，保存相加等于最小值的2个元素；再计算3个元素相加绝对值最小的，保存相加等于最小值的3个元素；一次类推，直到n(array.length)个元素相加绝对值最小，保存相加等于最小值的n个元素；最后在计算的1个元素相加和最小的，2个元素相加和最小，3个元素相加和最小，…… ，n（array.length）个元素相加和最小中找个最小值m，则m就是这个就是求和最近进0的，由相加和等于m的元素组成的数组就是所要求的子数组。

Answer 6

先加一个0进入数列
然后进行排序,接着：
记数列中就会出现N个正数，M个负数
记正数和为N1，负数和的绝对值为M1
如果N1<M1，剔除绝对值比M1大的数
如果M1<N1，剔除绝对值比N1大的数
任意取得正负两个数作为一个集合f（比如取得0左右两边的数），先假设这两个数相加后的绝对值 m最接近0，且记这两个相加后的和为k
如果k是正数，记该负数左右两边的值为a，b，正数或正数集合为m
计算{a}∪f，{b}∪f,{a,m}绝对值记为al，br，a1
判断 al，ar，a1，m 哪个最小

如果al或ar或a1是最小值，那么m=al或ar或a1，f等于所对应的集合
更新k，如果集合中有a值，那么从a的左边开始寻找一个数X，判断{X，m}的绝对值是否小于k
（这么做是防止f中出现跳数较大的情况）
如果有a的集合仍然是正数，则对{a的左值，f}的绝对值与f进行判断，直到不是正数或者到末尾为止
如果有b的集合仍然是正数，则对{b的右值，f}的绝对值与f进行判断，直到不是正数或者到末尾为止
如果al，ar，a1，m 中间有一个数等于0，则等于0的集合就是最接近0的数组

反之，如果是负数，则与正数类似

方法二 镜子法：
正数是负数的对立面，负数是正数的对立面
具体没想好，大致是这样的:
先对数列进行裁剪和排序
所谓镜子法，就是以一组都是负数或者是正数的为标准，去对照另一组数，求的相似度

该数列分为正数和负数两块 以负数为例，

负数的对立面也就是正数区，但这只是一个虚拟区域，需要真实数据去填充
换句话说，就是将负数区域的数的绝对值与正数去比较，在正数区域取得与负数区域绝对值最相似的数
以相似度进行排序
如果取得完全相似的数组则输出
如果没有取得，那以所求得的相似度作为数列（取不到最相似的数则将该数做为一个集合，其相似度即是该数）依照以上方法进行判断，
值得注意的是：此时以相似度排出的数列，已经近似等于数列的1/2，一直做下去就是1/4，1/8,1/16,1/32,1/64........................

而且有些数或者是集合可以通过裁剪的方式进行去除

依照顺序取数也可以，但这样效率是不是比取最相似数的效率高，目前还没有结论

Answer 7

可以将这个问题转化为没有重量上限（这里没有上限其实有个最大值，用宏定义下这个最大就行了）的背包问题。

Answer 8

可以用一个数组存储元素 一部分是大于0的 一部分是小于0的 如果有等于0的 那好 不用计算了 取出0就是结果

然后进行划分 首先如果只有负数的多个元素的划分 那么不可能最接近0 因为他们中每个元素都比这样的组合好

例如 123 -23 89 765 -41

然后划分负数部分
1、 -23
2、-41
3、-23 -41
划分正数部分
1、123
2、89

3、765
4、123、89
5、123、765
6、89、765
然后用复数部分与正数部分 分别相加 最接近0的组合 便可以产生了