合計が0のサブ配列があるかどうかを調べます


難易度 ミディアム
よく聞かれる Citrix社 DEショウ ゴールドマン·サックス 確かに 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. 配列をトラバースします。 i <n (配列の長さ)。
    1. 合計をarr [i]に追加し、合計に保存します。
    2. 次の条件のいずれかが当てはまるかどうかを確認します。
      1. sum == 0 / arr [i] == 0 / Setにsumの値が含まれている場合。
      2. trueの場合、trueを返します。
    3. 合計をセットに追加します。
  4. falseを返します。

説明

合計が0に等しいサブ配列が存在するかどうかを確認するように求める問題ステートメントを取得しました。これを解決するには、Setを使用してこの問題を解決します。 特定の配列の要素をセットに格納します。 次に、同時に値を合計に追加し、セット内の現在の合計とサブ配列が一致するかどうか、または合計自体が0に等しいかどうかを確認します。合計が0のサブ配列が見つかった場合は、次のようになります。本当。

合計が0であることが判明したサブ配列がない場合は、ループからfalseを返します。 また、要素のいずれかが0の場合、要素自体がXNUMXつの単一要素のサブ配列であるため、trueを返します。 つまり、そのようなサブアレイがXNUMXつ見つかったことを意味します。

ここでコードでは、ブール関数を宣言します。これはtrueまたはfalseのいずれかを返し、サブ配列が見つかった場合はtrueを返し、そうでない場合はfalseを返します。

例を考えてみましょう:

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

ここでのコードでは、配列をトラバースし、sumとarr [i]を追加してsumに格納し、その後、sum == 0またはarr [i]が0に等しいか、Setにsumの値が含まれているかどうかを確認します。指定された条件のいずれかが満たされた場合、trueを返し、合計をSetに追加します。

サブ配列が見つからない場合は、falseを返します。

sum = 0、Set = {}

i = 0、arr [i] = -3

合計=合計+ arr [i] => 0 + – 3 = -3

sum == 0またはarr [i]が0に等しいか、Setにsumの値が含まれている場合、そのうちの3つはfalseであるため、ここでは何もせずに-XNUMXをSetに追加します。

i = 1、arr [i] = 2

合計=合計+ arr [i] => -3 + 2 = -1

sum == 0またはarr [i]が0に等しいか、Setにsumの値が含まれている場合、そのうちの1つはfalseであるため、ここでは何もせずに-XNUMXをSetに追加します。

i = 2、arr [i] = 1

合計=合計+ arr [i] => -1 + 1 = 0

ここでsum == 0の条件が満たされている場合、trueを返すと、sum0のサブ配列が見つかったことを意味します。

出力:はい、合計が0のサブ配列が存在します。

コード

合計が0のサブ配列があるかどうかを調べるC ++コード

#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) where 「n」 配列内の要素の数です。 HashSetを使用すると、O(1)時間で挿入、検索、削除を実行できるため、これらすべてが可能になりました。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 作成されたハッシュセットには最大でn個の要素が含まれる可能性があるため、スペースの複雑さは線形です。