제로섬으로 모든 트리플렛 찾기-TutorialCup

“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 쌍입니다.

암호알고리즘

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

복잡성 분석

시간 복잡성

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

공간 복잡성

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

Twitter Facebook 링크드 인 버퍼 레딧 텀블러