查找是否有一个总和为0的子数组  


难度级别 中等
经常问 思杰 高盛 的确 MakeMyTrip OYO房间 Paytm TCS
排列 哈希

问题“查找是否有一个总和为0的子数组”指出给您一个 整数 排列 也包含负整数。 问题陈述要求确定是否有至少为1的大小的子数组。此子数组的总和应等于1。

使用案列  

查找是否有一个总和为0的子数组

arr[] = {2,1,-3,4,5}
yes

说明

在这里,从索引0到2的元素的总和为0。

arr[] = {4,1,-4,5,1}
yes

说明

不存在总和为0的子数组。

算法  

  1. 声明一个 .
  2. 初始化 总和 到0。
  3. 遍历数组,而 我<n (数组的长度)。
    1. 将sum加到arr [i]并将其存储到sum。
    2. 检查以下条件是否为真:
      1. sum == 0 / arr [i] == 0 /如果Set包含sum的值。
      2. 如果为true,则返回true。
    3. 将总和添加到集合中。
  4. 返回false。

说明

我们得到了一个问题陈述,要求找出是否存在总和等于0的子数组。要解决此问题,我们将使用Set来解决此问题。 我们将把给定数组的元素存储到Set中。 然后同时将值添加到总和中,并检查子数组是否与集合中的当前总和匹配,或者总和本身等于0。如果发现子总和为0,则我们将返回真的。

如果没有一个子数组的总和为0,那么我们将在循环外返回false。 同样,有一件事,如果任何一个元素为0,那么我们也将返回true,因为一个元素本身就是一个单个元素的子数组。 因此,这意味着我们找到了一个这样的子阵列。

参见
素数频率大于或等于k的数

在代码中,我们声明一个布尔函数,它将返回true或false,如果找到子数组,则返回true,否则将返回false。

让我们考虑一个例子:

使用案列

arr [] = {-3,2,1,9,6}

在代码中,我们将遍历一个数组,将sum和arr [i]相加并存储到sum中,然后进行检查,如果sum == 0或arr [i]等于0或Set包含sum的值,如果满足任何给定条件,则我们将返回true,然后将sum加到Set中。

如果没有找到任何子数组,那么我们将返回false。

sum = 0,Set = {}

i = 0,arr [i] = -3

sum = sum + arr [i] => 0 + – 3 = -3

如果sum == 0或arr [i]等于0或Set包含sum的值,则其中三个为假,因此我们在此处不执行任何操作,并将-3加到Set中。

i = 1,arr [i] = 2

sum = sum + arr [i] => -3 + 2 = -1

如果sum == 0或arr [i]等于0或Set包含sum的值,则其中三个为假,因此我们在此处不执行任何操作,并将-1加到Set中。

i = 2,arr [i] = 1

sum = sum + arr [i] => -1 + 1 = 0

如果这里满足sum == 0的条件,那么我们返回true,这意味着我们找到了一个总和为0的子数组。

输出:是,存在一个总和为0的子数组。

代码  

用C ++代码查找是否存在总和为0的子数组

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

用于查找是否存在总和为0的子数组的Java代码

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 所有这些都是可能的,因为使用了HashSet,因为它允许我们在O(1)时间内执行插入,搜索和删除。

参见
买卖股票II Leetcode解决方案的最佳时间

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 由于在创建的哈希集中最多可以有n个元素,因此空间复杂度是线性的。