给定一个整数数组，检测是否存在一个和为零的子数组

问题：给定一个整数数组，写一个算法实现判断是否存在一个和为零的子数组。

答：算法思路：计算数组的前缀和，然后将前缀和进行排序，如果存在连续两个元素相同的情况即存在一个和为零的子数组，否则不存在。

算法的代码实现：

//
//  main.cpp
//  MyProjectForCPP
//
//  Created by labuser on 11/2/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <math.h>

#define     YES     1
#define     NO      0

using namespace std;


void sort(int x[],int n);

int zero_sum(int x[],int n){
    int i;
    
    for(i=1;i<n;i++){
        x[i]+=x[i-1];
    }
    
    sort(x,n);
    
    for(i=1;i<n && x[i]!=x[i-1];i++);
    
    return (i==n) ? NO : YES;
}

void sort(int x[],int n){
    int i,j;
    int temp;
    
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(x[i]>x[j]){
                temp = x[i];
                x[i]=x[j];
                x[j]=temp;
            }
        }
    }
}

int main (int argc, const char * argv[])
{
    int x[] = {4,-1,2,1,-2,-1,5};
    int n = sizeof(x)/sizeof(int);
    int i;
    
    printf("\nZero Sum Sunarray Check Program");
    printf("\n===============================");
    printf("\n\nGiven Array : ");
    
    for(i=0;i<n;i++)
        printf("%4d",x[i]);
    
    if (zero_sum(x, n)==YES) {
        printf("\n\nYES, there is some range summing up to 0");
    }else{
        printf("\n\nNO! no such subarray found!");
    }
    
    printf("\n\n");
    
    return 0;
}

运行结果：
GNU gdb 6.3.50-20050815 (Apple version gdb-1705) (Fri Jul  1 10:44:54 UTC 2011)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin".tty /dev/ttys002
[Switching to process 17846 thread 0x0]

Zero Sum Sunarray Check Program
===============================

Given Array :    4  -1   2   1  -2  -1   5

YES, there is some range summing up to 0

Program ended with exit code: 0

评论

1 楼 liuxbgiant 2013-08-28  

上面代码有些问题，可以与QQ：447369396交流……