查找是否有一個總和為0的子數組


難度級別
經常問 思傑 高盛 確實 我的旅行 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,因為一個元素本身就是一個單個元素的子數組。 因此,這意味著我們找到了一個這樣的子陣列。

在代碼中,我們聲明一個布爾函數,它將返回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)時間內執行插入,搜索和刪除。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 由於在創建的哈希集中最多可以有n個元素,因此空間複雜度是線性的。