Βρείτε ένα τριπλό άθροισμα σε μια δεδομένη τιμή  


Για να βρείτε ένα τρίδυμο που συνοψίζει ένα πρόβλημα με δεδομένη τιμή που έχουμε δώσει παράταξη ακέραιων αριθμών (θετικοί και αρνητικοί αριθμοί) και πρέπει να βρείτε ένα τρίδυμο (3 στοιχεία) σε πίνακα του οποίου το άθροισμα είναι ίσο με τη δεδομένη τιμή X.

Μορφή εισόδου  

Πρώτη γραμμή που περιέχει δύο ακέραιες τιμές N και X.

Δεύτερη γραμμή που περιέχει N ακέραιες τιμές ή πίνακα εισαγωγής.

Μορφή εξόδου  

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

Περιορισμοί  

  • 1 <= Ν <= 100000
  • -1e9 <= α [i] <= 1e9
  • -1e9 <= X <= 1e9

Παραδείγματα  

Εισαγωγή

6, 10

1, 5, 7, 3, 4, 2
Παραγωγή

1 7 2

Εισαγωγή

8, 11

-1, 12, 5, 7, -2, -4, 5, 1
Παραγωγή

-2 1 12

Εισαγωγή

8, 0

-1, 12, 5, 7, -2, -4, 5, 1
Παραγωγή

-4 -1 5

Προσέγγιση με τη χρήση 3 δεικτών για εύρεση τριπλού που αθροίζει μια δεδομένη τιμή  

    1. Ταξινομήστε πρώτα τον δεδομένο πίνακα που θα μας δώσει την πολυπλοκότητα του χρόνου (n log n)
    2. Πάρτε 3 δείκτες p1, p2, p3 όπου το p1 δείχνει προς την αρχή του πίνακα, το p2 θα δείχνει δίπλα στο p1 και το p3 θα δείχνει στον τελευταίο δείκτη ενός πίνακα.
      Βρείτε ένα τριπλό άθροισμα σε μια δεδομένη τιμήΚαρφώστε
    3. Έχετε ένα loop1 για μετακίνηση (αύξηση) p1 έως p1 <p3
    4. Για κάθε επανάληψη του βρόχου1 έχετε το loop2 για να μετακινήσετε (αύξηση) p2 έως το p2 <p3
    5. Εάν το άθροισμα της σειράς [p1] + Array [p2] + Array [p3]> k τότε η μείωση p3
    6. Εάν το άθροισμα της σειράς [p1] + Array [p2] + Array [p3] == k τότε Εκτυπώστε τα στοιχεία
    7. p2 = p1 +1 και p3 = Array.length - 1
Βλέπε επίσης
Infix στο Postfix

 Πρόγραμμα C ++ για την εύρεση ενός τριπλού που αθροίζει μια δεδομένη τιμή

#include <bits/stdc++.h>
using namespace std;
void findTriplets(int arr[], int n, int k)
 {
      sort(arr,arr+n);
      int p1=0, p2, p3, counter=0;
      p2 = p1 + 1;
      p3 = n-1;
    while(p1<p3)
    {
       while(p2<p3) 
       { 
          if((arr[p1] + arr[p2] + arr[p3]) > k)
          p3--;
          if(((arr[p1] + arr[p2] + arr[p3]) == k)&&(p2<p3)) 
          {
              cout<<arr[p1]<<" "<<arr[p2]<<" "<<arr[p3]<<endl;
              counter++; 
              goto label;
          } 
          p2++; 
       } 
       p1++; 
       p2=p1+1; 
       p3=n-1; 
    } 
    if(counter==0) 
    cout<<0<<endl;
    label:; 
} 
int main()
{
    int n,x;
    cin>>n>>x;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    findTriplets(a,n,x);
    return 0;
}
6 10
1 5 7 3 4 2
1 2 7

Ανάλυση πολυπλοκότητας για εύρεση τριάδας που αθροίζεται σε δεδομένη τιμή

Χρόνος πολυπλοκότητας

O (n * n * n) όπου n είναι το μήκος του πίνακα. Εδώ χρησιμοποιούμε τη μέθοδο 3 δεικτών για να διασχίσουμε τον πίνακα. Στη χειρότερη περίπτωση, ο βρόχος θα τρέξει N * N * N φορές.

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

O (1) γιατί εδώ δεν χρησιμοποιούμε κανένα βοηθητικό χώρο εδώ.

Προσέγγιση 2 για να βρείτε ένα τρίδυμο που αθροίζει μια δεδομένη τιμή  

Εδώ επίσης πρέπει να βρούμε τα τρίδυμα από έναν πίνακα του οποίου το άθροισμα είναι ίσο με τον δεδομένο αριθμό.

Αλγόριθμος

1. Πρώτα ταξινομήστε τον πίνακα εισαγωγής
2. Διορθώστε το πρώτο στοιχείο ως arr [i], όπου κυμαίνεται από 0 έως N-2

3. Αφού διορθώσετε το πρώτο στοιχείο, για να βρείτε τα επόμενα δύο στοιχεία, πάρτε δύο δείκτες όπως μεταβλητές (j = i + 1, k = N-1) και διασχίστε τον αλγόριθμο για να βρείτε το άθροισμα σε ταξινομημένη συστοιχία.

4. ενώ το j είναι μικρότερο από k Προσθέστε τα στοιχεία στα δεδομένα ευρετήρια, δηλαδή, arr [i] + arr [j] + arr [k] εάν το άθροισμα Triplet είναι ίσο με την τιμή X, εκτυπώστε τα τρία άλλα στοιχεία εάν το άθροισμα Triplet είναι μικρότερη από την τιμή X, τότε αυξήστε την τιμή j αλλιώς μειώστε την τιμή του k.

Βρείτε ένα τριπλό άθροισμα σε μια δεδομένη τιμήΚαρφώστε

Πρόγραμμα C ++ για την εύρεση ενός τριπλού που αθροίζει μια δεδομένη τιμή

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    cin>>n>>x;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int flag=0;
    sort(a,a+n);//sort the array in ascending order
    int computed_sum;//sum computed at each step
    //fix one element and search for other two elements in linear time
    for(int i = 0; i <n-2; i++) 
    {
      //jth index starts from the next element of selected and k always starts at the ending index
      int j = i+1,k=n-1; 
      while(j<k)
      {
         //add the elements at the given indices 
         computed_sum=a[i]+a[j]+a[k]; 
         if(computed_sum==x)
         {
            cout<<a[i]<<" "<<a[j]<<" "<<a[k];
            return 1;
         }
         else if(computed_sum<x)
         {
            k--;
         }
         else
         {
            j++;
         }
      }
    }
    cout<<0<<endl;
  return 0;
}
8 0
-1 12 5 7 -2 -4 5 1
-4 -1 5

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ2) όπου N είναι το μέγεθος του πίνακα. Εδώ διορθώνουμε το I και στη συνέχεια χρησιμοποιούμε δύο μεθόδους δείκτη για τις τιμές j και k. Αυτό θα πάρει χρόνο N * N στη χειρότερη περίπτωση.

Βλέπε επίσης
Καταμέτρηση και εναλλαγή ερωτημάτων σε δυαδική σειρά

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

Ο (1) γιατί δεν χρησιμοποιούμε κανένα βοηθητικό χώρο.

αναφορές