Βρείτε όλα τα τρίδυμα με μηδενικό άθροισμα


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα GE Healthcare Google Πεζοπορώ
Παράταξη Χασίσι Αναζήτηση Ταξινόμηση

Το πρόβλημα "Εύρεση όλων των τριπλών με μηδενικό άθροισμα" δηλώνει ότι σας δίνεται ένας πίνακας που περιέχει θετικό και αρνητικό αριθμό και τα δύο. Η δήλωση προβλήματος ζητά να μάθει το τρίδυμο με το άθροισμα ίσο με 0.

Βρείτε όλα τα τρίδυμα με μηδενικό άθροισμα

Παράδειγμα

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

Αλγόριθμος

  1. Είδος τον δεδομένο πίνακα.
  2. Ρυθμίστε το Boolean μεταβλητή βρίσκεται σε ψευδές.
  3. Βρόχος από i = 0 έως i
    1. σετ fir = i + 1, sec = n-1 και μια άλλη μεταβλητή x στο τρέχον στοιχείο πίνακα.
    2. Ενώ έλατο
      1. Ελέγξτε εάν τρία από τα στοιχεία σχηματίζουν μαζί ένα άθροισμα 0.
        1. Εάν είναι αλήθεια, τότε εκτυπώστε και τους τρεις αριθμούς και ορίστε το isFound to true.
      2. Ελέγξτε εάν το άθροισμα τριών στοιχείων (τρέχοντα στοιχεία πίνακα) είναι μικρότερο από 0.
        1. Εάν ισχύει, αυξήστε την τιμή του έλατου κατά 1.
      3. Ελέγξτε εάν το άθροισμα των τριών στοιχείων είναι μεγαλύτερο από 0.
          1. Εάν ισχύει, μειώστε την τιμή του δευτερολέπτου κατά 1.
  4. Ελέγξτε εάν το isFound παραμένει ψευδές, αυτό σημαίνει ότι δεν μπορούν να σχηματιστούν τρίδυμα.

εξήγηση

Μας δίνεται ένας πίνακας. Στη συνέχεια, μας ζητείται να προσδιορίσουμε τα τρίδυμα που μπορούν να σχηματιστούν με τους δεδομένους αριθμούς σε έναν πίνακα του οποίου το άθροισμα είναι 0. Θα χρησιμοποιήσουμε έναν ένθετο βρόχο. Αυτός ο αλγόριθμος μπορεί να λειτουργεί σε σταθερό χώρο. Πρώτον, θα ταξινομήσουμε τον πίνακα. Με αυτόν τον τρόπο μπορούμε να χρησιμοποιήσουμε την τεχνική δύο δεικτών. Θα δηλώσουμε μια μεταβλητή Boolean και θα ορίσουμε την τιμή της σε false αρχικά. Αυτό είναι απλώς για να διασφαλιστεί εάν δεν θα βρούμε κανένα από τα τρίδυμα που έχουν στοιχεία άθροισμα 0, η τιμή του βρίσκεται μένει να είναι ψεύτικο. Τότε θα το ενημερώσουμε σε true όποτε βρίσκουμε ένα τρίδυμο. Έτσι, μπορούμε να συμπεράνουμε ότι δεν βρέθηκε τρίδυμο.

Θα ταξινομήσουμε πρώτα τον πίνακα, στον ένθετο βρόχο. Στη συνέχεια, διασχίζουμε τον πίνακα έως το n-1. Θα ορίσουμε την αρχική τιμή ως i + 1, τελευταία τιμή σε n-1 και x στην τρέχουσα τιμή στον εξωτερικό βρόχο. Στον εσωτερικό βρόχο θα διασχίσουμε τις τιμές ενός πίνακα και θα ελέγξουμε εάν το άθροισμα και των τριών στοιχείων (x + arr [fir] + arr [sec]) είναι ίσο με 0 ή όχι. Αν βρεθεί ότι είναι 0, αυτό σημαίνει ότι βρήκαμε το πρώτο ζεύγος και εκτυπώσαμε όλες τις τρέχουσες τιμές ενός πίνακα και ορίστε την τιμή isFound σε true.

Αυτό δείχνει ότι έχουμε βρει ένα από τα ζεύγη. Εάν το άθροισμα του τριπλού δεν είναι ίσο με το 0. Ελέγουμε αν το άθροισμα τριών τρεχόντων στοιχείων είναι μικρότερο από 0. Εάν το άθροισμα είναι μικρότερο από 0. Αυξάνουμε το fir, σημαίνει ότι η αρχική μας τιμή αυξάνεται. Εάν η κατάσταση δεν ικανοποιείται. Ελέγχουμε αν το άθροισμα είναι μεγαλύτερο από 0. Εάν ισχύει, τότε μείωση δευτ.

Με αυτόν τον τρόπο, θα βρούμε όλα τα πιθανά τρίδυμα που μπορούν να είναι άθροισμα 0.

Κωδικός 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)

Κωδικός Java για εύρεση όλων των τριπλών με μηδενικό άθροισμα

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) χρόνο.

Διαστημική πολυπλοκότητα

Ο (1) καθώς δεν απαιτείται επιπλέον χώρος.