Encuentra si hay un subarreglo con suma 0

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *