子數(shù)組和最接近零問題：

對于長度為N的數(shù)組A，求連續(xù)子數(shù)組的和最接近0的值。

如：1，-2，3，10，-4，7，2，-5；該數(shù)組中子數(shù)組和最接近零的值為0，子數(shù)組為-4，7，2，-5。

程序?qū)崿F(xiàn)：

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 }

運行結(jié)果：

說明：本算法時間復(fù)雜度為O(nlogn)。

轉(zhuǎn)載請注明出處：

C++博客園：godfrey_88

http://www.cnblogs.com/gaobaoru-articles/

轉(zhuǎn)載于:https://www.cnblogs.com/gaobaoru-articles/p/5456710.html

總結(jié)

以上是生活随笔為你收集整理的子数组和最接近零问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。