给定一个整数数组,检测是否存在一个和为零的子数组
程序员文章站
2024-02-03 16:54:16
...
问题:给定一个整数数组,写一个算法实现判断是否存在一个和为零的子数组。
答:算法思路:计算数组的前缀和,然后将前缀和进行排序,如果存在连续两个元素相同的情况即存在一个和为零的子数组,否则不存在。
算法的代码实现:
运行结果:
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
答:算法思路:计算数组的前缀和,然后将前缀和进行排序,如果存在连续两个元素相同的情况即存在一个和为零的子数组,否则不存在。
算法的代码实现:
//
// 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
上一篇: 苹果电脑怎么关机 Mac系统关机快捷键及关机方法介绍
下一篇: 单链表的九种基本操作(2021.5)
推荐阅读
-
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
-
给定一个整数数组,检测是否存在一个和为零的子数组
-
给定一个正序的整形数组A和一个数X,判断数组A里面是否存在两个数,他们的和为X;
-
刷题之给定一个整数数组 nums 和一个目标值 taget,请你在该数组中找出和为目标值的那 两个 整数
-
算法题:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
LeetCode 1 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
-
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
-
两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。...
-
c语言和Java语言实现,两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。