子数组和最接近零问题：
对于长度为N的数组A，求连续子数组的和最接近0的值。
如：1，-2，3，10，-4，7，2，-5；该数组中子数组和最接近零的值为0，子数组为-4，7，2，-5。
程序实现：
1 /*************************************** 2 FileName NearZeroSubArray.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/3 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int NearZeroSubArray(int* A,int size){ 16 int sum[size+1]; 17 memset(sum,0,(size+1)*sizeof(int)); 18 for(int i=1;i<size;i++){ 19 sum[i+1] = sum[i] + A[i]; 20 } 21 sort(sum,sum+size+1); 22 int difference = abs(sum[1] - sum[0]); 23 int result = difference; 24 for(int i=1;i<size;i++){ 25 difference = sum[i+1] - sum[i]; 26 result = min(difference,result); 27 } 28 return result; 29 } 30 int main() 31 { 32 int a[] = {1,-2,3,10,-4,7,2,-5}; 33 int result = NearZeroSubArray(a,sizeof(a)/sizeof(int)); 34 cout<<"the FindNearZeroNum: "; 35 cout<<result<<endl; 36 return 0; 37 }
运行结果：
说明：本算法时间复杂度为O(nlogn)。
转载请注明出处：
C++博客园：godfrey_88