Рубрики

Найдите три элемента из трех разных массивов, таких что a + b + c = sum

Учитывая три целочисленных массива и «сумму», задача состоит в том, чтобы проверить, существуют ли три элемента a, b, c, такие, что a + b + c = сумма и a, b и c принадлежат трем различным массивам.

Примеры :

Input : a1[] = { 1 , 2 , 3 , 4 , 5 };
    a2[] = { 2 , 3 , 6 , 1 , 2 };
    a3[] = { 3 , 2 , 4 , 5 , 6 };  
        sum = 9
Output : Yes
1  + 2  + 6 = 9  here 1 from a1[] and 2 from
a2[] and 6 from a3[]   
    
Input : a1[] = { 1 , 2 , 3 , 4 , 5 };
    a2[] = { 2 , 3 , 6 , 1 , 2 };
    a3[] = { 3 , 2 , 4 , 5 , 6 };   
         sum = 20 
Output : No

Наивный подход состоит в том, чтобы запустить три цикла и проверить сумму трех элементов в разных массивах, равную заданному числу, если find, затем print существуют, а в противном случае print не существуют.

C ++

// C ++ программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма
#include<bits/stdc++.h>

using namespace std;

  
// Функция для проверки, если есть
// элемент из каждого массива такой
// эта сумма трех элементов
// равно заданной сумме.

bool findTriplet(int a1[], int a2[], 

                 int a3[], int n1, 

                 int n2, int n3, int sum)

{

    for (int i = 0; i < n1; i++)

    for (int j = 0; j < n2; j++)

        for (int k = 0; k < n3; k++)

            if (a1[i] + a2[j] + a3[k] == sum)

            return true;

  

    return false;

}

  
// Код драйвера

int main()

{

    int a1[] = { 1 , 2 , 3 , 4 , 5 };

    int a2[] = { 2 , 3 , 6 , 1 , 2 };

    int a3[] = { 3 , 2 , 4 , 5 , 6 };

    int sum = 9;

    int n1 = sizeof(a1) / sizeof(a1[0]);

    int n2 = sizeof(a2) / sizeof(a2[0]);

    int n3 = sizeof(a3) / sizeof(a3[0]);

    findTriplet(a1, a2, a3, n1, n2, n3, sum)?

                cout << "Yes" : cout << "No";

    return 0;

}

Джава

// Java программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма

class GFG 

{

          

    // Функция для проверки, если есть

    // элемент из каждого массива такой

    // эта сумма трех элементов

    // равно заданной сумме.

    static boolean findTriplet(int a1[], int a2[], 

                               int a3[], int n1, 

                               int n2, int n3, int sum)

    {

        for (int i = 0; i < n1; i++)

            for (int j = 0; j < n2; j++)

                for (int k = 0; k < n3; k++)

                    if (a1[i] + a2[j] + a3[k] == sum)

                    return true;

      

        return false;

    }

      

    // Код драйвера

    public static void main (String[] args)

    {

        int a1[] = { 1 , 2 , 3 , 4 , 5 };

        int a2[] = { 2 , 3 , 6 , 1 , 2 };

        int a3[] = { 3 , 2 , 4 , 5 , 6 };

        int sum = 9;

          

        int n1 = a1.length;

        int n2 = a2.length;

        int n3 = a3.length;

          

        if(findTriplet(a1, a2, a3, n1, n2, n3, sum))

            System.out.print("Yes");

        else

            System.out.print("No");

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для поиска
# три элемента из разных
# три массива такие, что
# a + b + c равно
# заданная сумма

  
# Функция для проверки, если есть
# является элементом каждого
# массив такой, что сумма
# три элемента равно
# заданная сумма.

def findTriplet(a1, a2, a3, 

                n1, n2, n3, sum):

  

    for i in range(0 , n1):

        for j in range(0 , n2):

            for k in range(0 , n3):

                if (a1[i] + a2[j] + 

                    a3[k] == sum):

                    return True

  

    return False

  
Код водителя

a1 = [ 1 , 2 , 3 , 4 , 5 ]

a2 = [ 2 , 3 , 6 , 1 , 2 ]

a3 = [ 3 , 2 , 4 , 5 , 6 ]

sum = 9

n1 = len(a1)

n2 = len(a2)

n3 = len(a3) 

print("Yes") if findTriplet(a1, a2, a3, 

                            n1, n2, n3, 

                            sum) else print("No")

  
# Этот код добавлен
# от Smitha

C #

// C # программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма

using System;

  

public class GFG

{

  
// Функция для проверки наличия
// элемент из каждого массива такой, что
// сумма трех элементов
// равно заданной сумме.

static bool findTriplet(int []a1, int []a2,

                        int []a3, int n1, 

                        int n2, int n3, 

                        int sum)

{

      

    for (int i = 0; i < n1; i++)

      

        for (int j = 0; j < n2; j++)

          

            for (int k = 0; k < n3; k++)

            if (a1[i] + a2[j] + a3[k] == sum)

            return true;

  

    return false;

}

  

    // Код драйвера

    static public void Main ()

    {

        int []a1 = {1 , 2 , 3 , 4 , 5};

        int []a2 = {2 , 3 , 6 , 1 , 2};

        int []a3 = {3 , 2 , 4 , 5 , 6};

        int sum = 9;

        int n1 = a1.Length;

        int n2 = a2.Length;

        int n3 = a3.Length;

        if(findTriplet(a1, a2, a3, n1,

                       n2, n3, sum))

        Console.WriteLine("Yes");

        else

        Console.WriteLine("No");

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма

  
// Функция для проверки наличия
// элемент из каждого массива такой, что
// сумма трех элементов равна
// до заданной суммы.

function findTriplet($a1, $a2, $a3

                     $n1, $n2, $n3

                     $sum)

{

    for ( $i = 0; $i < $n1; $i++)

    for ( $j = 0; $j < $n2; $j++)

        for ( $k = 0; $k < $n3; $k++)

            if ($a1[$i] + $a2[$j] + $a3[$k] == $sum)

            return true;

  

    return false;

}

  
// Код драйвера

$a1 = array( 1 , 2 , 3 , 4 , 5 );

$a2 = array( 2 , 3 , 6 , 1 , 2 );

$a3 = array( 3 , 2 , 4 , 5 , 6 );

$sum = 9;

$n1 = count($a1);

$n2 = count($a2);

$n3 = count($a3);

if(findTriplet($a1, $a2, $a3, $n1

               $n2, $n3, $sum)==true)

echo "Yes" ;

else

echo "No";

  
// Этот код предоставлен anuj_67.
?>


Выход :

Yes

Временная сложность: O (n 3 )
Пространство сложность: O (1)

Эффективным решением является сохранение всех элементов первого массива в хеш-таблице (unordered_set в C ++) и вычисление суммы двух элементов последних двух элементов массива один за другим, вычитание из заданного числа k и проверка в хеш-таблице, если она существует в хеш-таблице, тогда печать существует и в противном случае не существует.

1. Store all elements of first array in hash table
2. Generate all pairs of elements from two arrays using
   nested loop. For every pair (a1[i], a2[j]), check if
   sum - (a1[i] + a2[j]) exists in hash table. If yes
   return true.      

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма
#include<bits/stdc++.h>

using namespace std;

  
// Функция для проверки, если есть
// элемент из каждого массива такой
// эта сумма трех элементов
// равно заданной сумме.

bool findTriplet(int a1[], int a2[], 

                 int a3[], int n1, 

                 int n2, int n3, 

                 int sum)

{

    // Сохраняем элементы

    // первый массив в хэше

    unordered_set <int> s;

    for (int i = 0; i < n1; i++)

        s.insert(a1[i]);

  

    // суммируем последние два массива

    // элемент один за другим

    for (int i = 0; i < n2; i++)

    {

        for (int j = 0; j < n3; j++)

        {

            // Рассмотрим текущую пару и

            // найти, есть ли элемент

            // в a1 [] так, что эти три

            // формируем нужный триплет

            if (s.find(sum - a2[i] - a3[j]) != 

                                       s.end())

                return true;

        }

    }

  

    return false;

}

  
// Код драйвера

int main()

{

    int a1[] = { 1 , 2 , 3 , 4 , 5 };

    int a2[] = { 2 , 3 , 6 , 1 , 2 };

    int a3[] = { 3 , 2 , 4 , 5 , 6 };

    int sum = 9;

    int n1 = sizeof(a1) / sizeof(a1[0]);

    int n2 = sizeof(a2) / sizeof(a2[0]);

    int n3 = sizeof(a3) / sizeof(a3[0]);

    findTriplet(a1, a2, a3, n1, n2, n3, sum)?

    cout << "Yes" : cout << "No";

  

    return 0;

}

Джава

// Java программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма

import java.util.*;

  

class GFG 

{

  

    // Функция для проверки, если есть

    // элемент из каждого массива такой

    // эта сумма трех элементов

    // равно заданной сумме.

    static boolean findTriplet(int a1[], int a2[], int a3[],

                                int n1, int n2, int n3,

                                int sum)

    {

        // Сохраняем элементы

        // первый массив в хэше

        HashSet<Integer> s = new HashSet<Integer>();

        for (int i = 0; i < n1; i++) 

        {

            s.add(a1[i]);

        }

  

        // суммируем последние два массива

        // элемент один за другим

        ArrayList<Integer> al = new ArrayList<>(s);

        for (int i = 0; i < n2; i++) 

        {

            for (int j = 0; j < n3; j++) 

            {

                  

                // Рассмотрим текущую пару и

                // найти, есть ли элемент

                // в a1 [] так, что эти три

                // формируем нужный триплет

                if (al.contains(sum - a2[i] - a3[j]) & 

                            al.indexOf(sum - a2[i] - a3[j])

                            != al.get(al.size() - 1)) 

                {

                    return true;

                }

            }

        }

        return false;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int a1[] = {1, 2, 3, 4, 5};

        int a2[] = {2, 3, 6, 1, 2};

        int a3[] = {3, 2, 4, 5, 6};

        int sum = 9;

        int n1 = a1.length;

        int n2 = a2.length;

        int n3 = a3.length;

        if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) 

        {

            System.out.println("Yes");

        }

        else

        {

            System.out.println("No");

        }

    }

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для поиска трех элементов
# из разных трех массивов таких
# что a + b + c равно
# заданная сумма

  
# Функция для проверки, если есть
# элемент из каждого массива такой
# эта сумма трех элементов
# равно заданной сумме.

def findTriplet(a1, a2, a3, 

                n1, n2, n3, sum):

  

    # Хранить элементы первого

    # массив в хэше

    s = set()

  

    # сумма последних двух элементов массива

    # по одному

    for i in range(n1):

        s.add(a1[i])

  

    for i in range(n2):

        for j in range(n3):

  

            # Рассмотрим текущую пару и

            # найти, если есть элемент

            # в a1 [] так, что эти три

            # сформировать нужный триплет

            if sum - a2[i] - a3[j] in s:

                return True

    return False

  
# Код драйвера

a1 = [1, 2, 3, 4, 5]

a2 = [2, 3, 6, 1, 2]

a3 = [3, 24, 5, 6]

n1 = len(a1)

n2 = len(a2)

n3 = len(a3)

sum = 9

if findTriplet(a1, a2, a3, 

               n1, n2, n3, sum) == True:

    print("Yes")

else:

    print("No")

  
# Этот код предоставлен Shrikant13

C #

// C # программа для поиска трех элементов
// из трех разных массивов таких
// что a + b + c равно
// заданная сумма

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Функция для проверки, если есть

    // элемент из каждого массива такой

    // эта сумма трех элементов

    // равно заданной сумме.

    static bool findTriplet(int []a1, int []a2, int []a3,

                                int n1, int n2, int n3,

                                int sum)

    {

        // Сохраняем элементы

        // первый массив в хэше

        HashSet<int> s = new HashSet<int>();

        for (int i = 0; i < n1; i++) 

        {

            s.Add(a1[i]);

        }

  

        // суммируем последние два массива

        // элемент один за другим

        List<int> al = new List<int>(s);

        for (int i = 0; i < n2; i++) 

        {

            for (int j = 0; j < n3; j++) 

            {

                  

                // Рассмотрим текущую пару и

                // найти, есть ли элемент

                // в a1 [] так, что эти три

                // формируем нужный триплет

                if (al.Contains(sum - a2[i] - a3[j]) & 

                            al.IndexOf(sum - a2[i] - a3[j])

                            != al[al.Count - 1]) 

                {

                    return true;

                }

            }

        }

        return false;

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        int []a1 = {1, 2, 3, 4, 5};

        int []a2 = {2, 3, 6, 1, 2};

        int []a3 = {3, 2, 4, 5, 6};

        int sum = 9;

        int n1 = a1.Length;

        int n2 = a2.Length;

        int n3 = a3.Length;

        if (findTriplet(a1, a2, a3, n1, n2, n3, sum)) 

        {

            Console.WriteLine("Yes");

        }

        else

        {

            Console.WriteLine("No");

        }

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход :

Yes


Временная сложность:
O (n 2 )
Вспомогательное пространство: O (n)

Ссылки :
http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-a-given-number

Эта статья предоставлена DANISH_RAZA 🙂 . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите три элемента из трех разных массивов, таких что a + b + c = sum

0.00 (0%) 0 votes