Dada una array de números positivos y negativos, encuentre si hay una subarreglo (de tamaño al menos uno) con suma 0.
Ejemplos:
C++
// A C++ program to find if
// there is a zero sum subarray
#include <bits/stdc++.h>
using namespace std;
bool subArrayExists(int arr[], int n)
{
unordered_set<int> sumSet;
// Traverse through array
// and store prefix sums
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
// If prefix sum is 0 or
// it is already present
if (sum == 0
|| sumSet.find(sum)
!= sumSet.end())
return true;
sumSet.insert(sum);
}
return false;
}
// Driver code
int main()
{
int arr[] = { -3, 2, 3, 1, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (subArrayExists(arr, n))
cout << "Found a subarray with 0 sum";
else
cout << "No Such Sub Array Exists!";
return 0;
}
Java
// A Java program to find
// if there is a zero sum subarray
import java.util.HashSet;
import java.util.Set;
class ZeroSumSubarray
{
// Returns true if arr[]
// has a subarray with sero sum
static Boolean subArrayExists(int arr[])
{
// Creates an empty hashset hs
Set<Integer> hs = new HashSet<Integer>();
// Initialize sum of elements
int sum = 0;
// Traverse through the given array
for (int i = 0; i < arr.length; i++)
{
// Add current element to sum
sum += arr[i];
// Return true in following cases
// a) Current element is 0
// b) sum of elements from 0 to i is 0
// c) sum is already present in hash set
if (arr[i] == 0
|| sum == 0
|| hs.contains(sum))
return true;
// Add sum to hash set
hs.add(sum);
}
// We reach here only when there is
// no subarray with 0 sum
return false;
}
// Driver code
public static void main(String arg[])
{
int arr[] = { -3, 2, 3, 1, 6 };
if (subArrayExists(arr))
System.out.println(
"Found a subarray with 0 sum");
else
System.out.println("No Such Sub Array Exists!");
}
}
Python3
# A python program to find if
# there is a zero sum subarray
def subArrayExists(arr, n):
# traverse through array
# and store prefix sums
n_sum = 0
s = set()
for i in range(n):
n_sum += arr[i]
# If prefix sum is 0 or
# it is already present
if n_sum == 0 or n_sum in s:
return True
s.add(n_sum)
return False
# Driver code
arr = [-3, 2, 3, 1, 6]
n = len(arr)
if subArrayExists(arr, n) == True:
print("Found a sunbarray with 0 sum")
else:
print("No Such sub array exits!")
# This code is contributed by Shrikant13
C#
// A C# program to find if there
// is a zero sum subarray
using System;
using System.Collections.Generic;
class GFG {
// Returns true if arr[] has
// a subarray with sero sum
static bool SubArrayExists(int[] arr)
{
// Creates an empty HashSet hM
HashSet<int> hs = new HashSet<int>();
// Initialize sum of elements
int sum = 0;
// Traverse through the given array
for (int i = 0; i < arr.Length; i++)
{
// Add current element to sum
sum += arr[i];
// Return true in following cases
// a) Current element is 0
// b) sum of elements from 0 to i is 0
// c) sum is already present in hash set
if (arr[i] == 0
|| sum == 0
|| hs.Contains(sum))
return true;
// Add sum to hash set
hs.Add(sum);
}
// We reach here only when there is
// no subarray with 0 sum
return false;
}
// Main Method
public static void Main()
{
int[] arr = { -3, 2, 3, 1, 6 };
if (SubArrayExists(arr))
Console.WriteLine(
"Found a subarray with 0 sum");
else
Console.WriteLine("No Such Sub Array Exists!");
}
}
Javascript
// A Javascript program to
// find if there is a zero sum subarray
const subArrayExists = (arr) => {
const sumSet = new Set();
// Traverse through array
// and store prefix sums
let sum = 0;
for (let i = 0 ; i < arr.length ; i++)
{
sum += arr[i];
// If prefix sum is 0
// or it is already present
if (sum === 0 || sumSet.has(sum))
return true;
sumSet.add(sum);
}
return false;
}
// Driver code
const arr = [-3, 2, 3, 1, 6];
if (subArrayExists(arr))
console.log("Found a subarray with 0 sum");
else
console.log("No Such Sub Array Exists!");
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA