제로섬을 가진 모든 트리플렛 찾기

난이도 중급
자주 묻는 질문 아마존 GE 헬스 케어 구글 인상
배열 해시 수색 정렬조회수 79

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

“0 합계가있는 모든 트리플렛 찾기”문제는 양수와 음수를 모두 포함하는 배열이 제공된다는 것을 나타냅니다. 문제 설명은 합계가 XNUMX 인 삼중 항을 찾아야합니다.

제로섬을 가진 모든 트리플렛 찾기

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

설명

이것들은 합이 0 인 세 쌍둥이입니다.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

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

설명

숫자의 합이 0 ⇒ -5 + 2 + 3 = 0 인 XNUMX 쌍입니다.

암호알고리즘

  1. 종류 주어진 배열.
  2. 설정 부울 변수 isFound 거짓으로.
  3. i = 0에서 i로 반복
    1. 세트 전나무 = i + 1, 초 = n-1 그리고 다른 변수 x 현재 배열 요소에.
    2. 전나무 동안
      1. 세 요소가 함께 0의 합계를 형성하는지 확인합니다.
        1. true이면 세 숫자를 모두 인쇄하고 isFound를 true로 설정합니다.
      2. 세 요소 (현재 배열 요소)의 합이 0보다 작은 지 확인합니다.
        1. 참이면 fir 값을 1 씩 늘립니다.
      3. 세 요소의 합이 0보다 큰지 확인하십시오.
          1. 참이면 sec 값을 1만큼 줄입니다.
  4. isFound가 거짓으로 남아 있는지 확인하십시오. 즉, XNUMX 중 요소가 형성 될 수 없음을 의미합니다.

설명

배열이 주어집니다. 그런 다음 합이 0 인 배열에서 주어진 숫자로 형성 할 수있는 0 중항을 결정하라는 요청을받습니다. 중첩 루프를 사용할 것입니다. 이 알고리즘은 일정한 공간에서 작동 할 수 있습니다. 먼저 배열을 정렬 할 것입니다. 이런 식으로 우리는 두 포인터 기법을 사용할 수 있습니다. 하나의 부울 변수를 선언하고 처음에는 그 값을 false로 설정합니다. 이것은 요소의 합이 XNUMX 인 트리플렛을 찾을 수 없는지 확인하기위한 것입니다. isFound 거짓으로 남아 있습니다. 그런 다음 트리플렛을 찾을 때마다 true로 업데이트합니다. 따라서 이것으로 우리는 삼중 항이 발견되지 않는다는 결론을 내릴 수 있습니다.

중첩 루프에서 배열을 먼저 정렬합니다. 그런 다음 배열을 n-1까지 순회합니다. 시작 값은 i + 1, 마지막 값은 n-1, x는 외부 루프의 현재 값으로 설정합니다. 내부 루프에서 배열의 값을 탐색하고 세 요소 (x + arr [fir] + arr [sec]) 모두의 합이 0인지 확인합니다. 0으로 확인되면 첫 번째 쌍을 찾고 배열의 현재 값을 모두 인쇄하고 isFound 값을 true로 설정했음을 의미합니다.

이것은 우리가 쌍 중 하나를 찾았 음을 나타냅니다. 삼중 항의 합이 0이 아니면 현재 세 요소의 합이 0보다 작은 지 확인합니다. 합이 0보다 작 으면 fir을 증가 시킨다는 것은 시작 값이 증가 함을 의미합니다. 조건이 만족되지 않는 경우. 합계가 0보다 큰지 확인합니다. 참이면 sec를 줄입니다.

이런 식으로 우리는 합이 0이 될 수있는 가능한 모든 삼중 항을 찾을 것입니다.

XNUMX 합계가있는 모든 트리플렛을 찾는 C ++ 코드

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

제로섬이있는 모든 트리플렛을 찾는 자바 코드

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

복잡성 분석

시간 복잡성

의 위에2) 어디에 "엔"  배열의 요소 수입니다. O (n) 시간에 기여하는 두 가지 포인터 기술을 사용하고 있기 때문입니다. 그러나 기술 자체는 O (n) 시간 동안 사용됩니다. 따라서 알고리즘이 O (n ^ 2) 시간에 실행됩니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다.

균열 시스템 설계 인터뷰
Translate »