합계가 0인 부분배열

난이도 중급
자주 묻는 질문 시트릭스 드 쇼 골드만 삭스 과연 MakeMyTrip 오요 룸 Paytm TCS
배열 해시조회수 40

"합이 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. arr [i]에 합계를 더하고 합계에 저장합니다.
    2. 다음 조건 중 하나라도 참인지 확인하십시오.
      1. sum == 0 / arr [i] == 0 / Set에 sum 값이 포함 된 경우.
      2. true이면 true를 반환합니다.
    3. 집합에 합계를 더합니다.
  4. 거짓을 반환합니다.

설명

우리는 합계가 0 인 하위 배열이 존재하는지 알아 내라는 문제 진술을 받았습니다.이를 해결하기 위해 우리는이 문제를 해결하기 위해 Set을 사용할 것입니다. 주어진 배열의 요소를 Set에 저장할 것입니다. 그런 다음 동시에 값을 합계에 추가하고 집합의 현재 합계와 일치하는 하위 배열이 있는지 또는 합계 자체가 0과 같은지 확인합니다. 합계가 0 인 하위 배열이 발견되면 다음을 반환합니다. 진실.

합계가 0 인 하위 배열이없는 경우 루프에서 false를 반환합니다. 또한 한 가지 요소가 0이면 요소 자체가 하나의 단일 요소의 하위 배열이기 때문에 true를 반환합니다. 그래서 그것은 우리가 그러한 하위 배열을 발견했음을 의미합니다.

여기 코드에서 Boolean 함수를 선언하면 true 또는 false를 반환하고 하위 배열이 발견되면 true를 반환하고 그렇지 않으면 false를 반환합니다.

예를 들어 보겠습니다.

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

여기 코드에서 우리는 배열을 순회하고 sum과 arr [i]를 더하고 sum에 저장하고 그 후에 sum == 0 또는 arr [i]가 0이거나 Set이 sum의 값을 포함한다면, 주어진 조건 중 하나라도 충족되면 true를 반환하고 합계를 Set에 추가합니다.

하위 배열이 발견되지 않으면 false를 반환합니다.

합계 = 0, 세트 = {}

i = 0, arr [i] = -3

합계 = 합계 + arr [i] => 0 + – 3 = -3

sum == 0 또는 arr [i]가 0이거나 Set에 sum의 값이 포함되어 있으면 그중 3 개는 false이므로 여기서는 아무것도하지 않고 Set에 -XNUMX을 더합니다.

i = 1, arr [i] = 2

합계 = 합계 + arr [i] => -3 + 2 = -1

sum == 0 또는 arr [i]가 0이거나 Set에 sum의 값이 포함되어 있으면 그중 1 개는 false이므로 여기서는 아무것도하지 않고 Set에 -XNUMX을 더합니다.

i = 2, arr [i] = 1

합계 = 합계 + arr [i] => -1 + 1 = 0

여기서 sum == 0 조건이 충족되면 true를 반환하면 합계가 0 인 하위 배열을 찾았 음을 의미합니다.

출력 : 예, 합계가 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) 어디에 "엔" 배열의 요소 수입니다. 이 모든 것은 HashSet을 사용했기 때문에 가능했습니다. O (1) 시간에 삽입, 검색, 삭제를 수행 할 수 있기 때문입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 생성 된 해시 세트에는 최대 n 개의 요소가있을 수 있으므로 공간 복잡성은 선형입니다.

Translate »
1