Όλα τα μοναδικά τρίδυμα που συνοψίζουν μια δεδομένη τιμή


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Απολύτως αμαζόνα Φανατικοί
Παράταξη Hashing Αναζήτηση

Έχουμε δώσει ένα παράταξη ακέραιων αριθμών και έναν δεδομένο αριθμό που ονομάζεται «άθροισμα» Η δήλωση προβλήματος ζητά να ανακαλύψει το τρίδυμο που προσθέτει τον δεδομένο αριθμό «άθροισμα».

Παράδειγμα

εισόδου:

arr [] = {3,5,7,5,6,1}

άθροισμα = 16

Παραγωγή:

(3, 7, 6), (5, 5, 6)

Επεξήγηση:

Τριπλό που ισούται με το δεδομένο άθροισμα.

εισόδου:

arr [] = {3,4,1,5,4}

άθροισμα = 20

Παραγωγή:

Δεν υπάρχουν τρίδυμα που μπορούν να σχηματιστούν με τον δεδομένο αριθμό

Αλγόριθμος

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

εξήγηση

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

Αφού ταξινομήσετε τον πίνακα, ξεκινώντας από τον ένθετο βρόχο, θα διασχίσουμε τον πίνακα μέχρι το μήκος n-1. Ορισμός μιας από τις μεταβλητές τιμές ως i + 1, μια άλλη τιμή σε n-1. Στον εσωτερικό βρόχο, θα διασχίσουμε όλες τις τιμές ενός πίνακα και θα ελέγξουμε εάν ο δεδομένος αριθμός «άθροισμα» είναι ίσος με το άθροισμα των τριών τρεχόντων στοιχείων συστοιχίας (arr [i] + arr [j] + arr [k ]) είναι ίσο ή όχι. Εάν η συνθήκη ικανοποιεί, θα εκτυπώσουμε όλες τις τρέχουσες τιμές ενός πίνακα και η τιμή isFound είναι αληθής, διασφαλίζει ότι δεν θα πρέπει να επιστρέψουμε μια λανθασμένη τιμή.

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

Θα συνεχιστεί μέχρι να διασταυρωθούν όλες οι τιμές του πίνακα. Και θα επιστρέψουμε την τιμή isFound, η οποία μπορεί να επιστραφεί ως αληθινή αν βρήκαμε κάποια από τα τρίδυμα και ψεύτικα εάν δεν βρήκαμε κανένα.

Εκτέλεση

Πρόγραμμα C ++ για όλα τα μοναδικά τρίδυμα που συνοψίζουν μια δεδομένη τιμή

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

Πρόγραμμα Java για όλα τα μοναδικά τρίδυμα που συνοψίζουν μια δεδομένη τιμή

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

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

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

Επί2όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.