Найдите три элемента из данных трех массивов, сумма которых равна X | Комплект 2
Для трех отсортированных целочисленных массивов A [] , B [] и C [] задача состоит в том, чтобы найти три целых числа, по одному из каждого массива, которые в сумме дают заданное целевое значение X. Выведите Yes или No в зависимости от того, существует такая тройка или нет.
Примеры:
Input: A[] = {2}, B[] = {1, 6, 7}, C[] = {4, 5}, X = 12
Output: Yes
A[0] + B[1] + C[0] = 2 + 6 + 4 = 12
Input: A[] = {2}, B[] = {1, 6, 7}, C[] = {4, 5}, X = 14
Output: Yes
A[0] + B[2] + C[1] = 2 + 7 + 5 = 14
Подход: в этой статье мы уже обсуждали подход на основе хеширования, который требует O (N) дополнительного места.
В этой статье мы решим эту проблему, используя метод экономии места, который требует O (1) дополнительного места. Идея заключается в использовании техники двух указателей.
Мы будем перебирать наименьший из всех массивов, и для каждого индекса i мы будем использовать два указателя на двух больших массивах, чтобы найти пару с суммой, равной X - A [i] (предполагая, что A [] является наименьшим из длина среди трех аррий).
Теперь, какова идея использования двух указателей на двух больших массивах? Попробуем понять то же самое на примере.
Let’s assume
len(A) = 100000
len(B) = 10000
len(C) = 10
Case 1: Applying two pointer on larger two arrays
Number of iterations will be of order = len(C) * (len(A) + len(B)) = 10 * (110000) = 1100000
Case 2: Applying two pointer on smaller two arrays
Number of iterations will be of order = len(A) * (len(B) + len(C)) = 100000 * (10010) = 1001000000
Case 3: Applying two pointer on smallest and largest array
Number of iterations will be of order = len(B) * (len(A) + len(C)) = 10000 * (100000 + 10) = 1000100000
As we can see, Case 1 is the most optimal for this example and it can be easily proved that its most optimal in general as well.
Алгоритм:
- Отсортируйте массивы в порядке возрастания их длины.
- Скажем, самый маленький массив после сортировки - это A []. Затем выполните итерацию по всем элементам A [] и для каждого индекса «i» примените два указателя к двум другим массивам. Мы поместим указатель в начало массива B [] и указатель на конец массива C []. Назовем указатель j и k соответственно.
- Если B [j] + C [k] = X - A [i], мы нашли совпадение.
- Если B [j] + C [k] меньше, чем X - A [i], мы увеличиваем значение 'j' на 1.
- Если B [j] + C [k] больше, чем X - A [i], мы уменьшаем значение k на 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if there// exists a triplet with sum xbool existsTriplet(int a[], int b[], int c[], int x, int l1, int l2, int l3){ // Sorting arrays such that a[] // represents smallest array if (l2 <= l1 and l2 <= l3) swap(l2, l1), swap(a, b); else if (l3 <= l1 and l3 <= l2) swap(l3, l1), swap(a, c); // Iterating the smallest array for (int i = 0; i < l1; i++) { // Two pointers on second and third array int j = 0, k = l3 - 1; while (j < l2 and k >= 0) { // If a valid triplet is found if (a[i] + b[j] + c[k] == x) return true; if (a[i] + b[j] + c[k] < x) j++; else k--; } } return false;}// Driver codeint main(){ int a[] = { 2, 7, 8, 10, 15 }; int b[] = { 1, 6, 7, 8 }; int c[] = { 4, 5, 5 }; int l1 = sizeof(a) / sizeof(int); int l2 = sizeof(b) / sizeof(int); int l3 = sizeof(c) / sizeof(int); int x = 14; if (existsTriplet(a, b, c, x, l1, l2, l3)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass GFG{// Function that returns true if there// exists a triplet with sum xstatic boolean existsTriplet(int a[], int b[], int c[], int x, int l1, int l2, int l3){ // Sorting arrays such that a[] // represents smallest array if (l2 <= l1 && l2 <= l3) { swap(l2, l1); swap(a, b); } else if (l3 <= l1 && l3 <= l2) { swap(l3, l1); swap(a, c); } // Iterating the smallest array for (int i = 0; i < l1; i++) { // Two pointers on second and third array int j = 0, k = l3 - 1; while (j < l2 && k >= 0) { // If a valid triplet is found if (a[i] + b[j] + c[k] == x) return true; if (a[i] + b[j] + c[k] < x) j++; else k--; } } return false;}private static void swap(int x, int y){ int temp = x; x = y; y = temp;}private static void swap(int []x, int []y){ int []temp = x; x = y; y = temp;}// Driver codepublic static void main(String[] args){ int a[] = { 2, 7, 8, 10, 15 }; int b[] = { 1, 6, 7, 8 }; int c[] = { 4, 5, 5 }; int l1 = a.length; int l2 = b.length; int l3 = c.length; int x = 14; if (existsTriplet(a, b, c, x, l1, l2, l3)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by Rajput-Ji |
Python3
# Function that returns True if there# exists a triplet with sum xdef existsTriplet(a, b,c, x, l1,l2, l3): # Sorting arrays such that a # represents smallest array if (l2 <= l1 and l2 <= l3): l1, l2 = l2,l1 a, b = b,a elif (l3 <= l1 and l3 <= l2): l1, l3 = l3,l1 a, c = c,a # Iterating the smallest array for i in range(l1): # Two pointers on second and third array j = 0 k = l3 - 1 while (j < l2 and k >= 0): # If a valid triplet is found if (a[i] + b[j] + c[k] == x): return True if (a[i] + b[j] + c[k] < x): j += 1 else: k -= 1 return False# Driver codea = [ 2, 7, 8, 10, 15 ]b = [ 1, 6, 7, 8 ]c = [ 4, 5, 5 ]l1 = len(a)l2 = len(b)l3 = len(c)x = 14if (existsTriplet(a, b, c, x, l1, l2, l3)): print("Yes")else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{// Function that returns true if there// exists a triplet with sum xstatic bool existsTriplet(int []a, int []b, int []c, int x, int l1, int l2, int l3){ // Sorting arrays such that a[] // represents smallest array if (l2 <= l1 && l2 <= l3) { swap(l2, l1); swap(a, b); } else if (l3 <= l1 && l3 <= l2) { swap(l3, l1); swap(a, c); } // Iterating the smallest array for (int i = 0; i < l1; i++) { // Two pointers on second and third array int j = 0, k = l3 - 1; while (j < l2 && k >= 0) { // If a valid triplet is found if (a[i] + b[j] + c[k] == x) return true; if (a[i] + b[j] + c[k] < x) j++; else k--; } } return false;}private static void swap(int x, int y){ int temp = x; x = y; y = temp;}private static void swap(int []x, int []y){ int []temp = x; x = y; y = temp;}// Driver codepublic static void Main(String[] args){ int []a = { 2, 7, 8, 10, 15 }; int []b = { 1, 6, 7, 8 }; int []c = { 4, 5, 5 }; int l1 = a.Length; int l2 = b.Length; int l3 = c.Length; int x = 14; if (existsTriplet(a, b, c, x, l1, l2, l3)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach// Function that returns true if there// exists a triplet with sum xfunction existsTriplet(a, b, c, x, l1, l2, l3){ // Sorting arrays such that a[] // represents smallest array if (l2 <= l1 && l2 <= l3) { temp = l1; l1 = l2; l2 = temp; temp = a; a = b; b = temp; } else if (l3 <= l1 && l3 <= l2) { temp = l1; l1 = l3; l3 = temp; temp = a; a = c; c = temp; } // Iterating the smallest array for (var i = 0; i < l1; i++) { // Two pointers on second and third array var j = 0, k = l3 - 1; while (j < l2 && k >= 0) { // If a valid triplet is found if (a[i] + b[j] + c[k] == x) return true; if (a[i] + b[j] + c[k] < x) j++; else k--; } } return false;}// Driver codevar a = [ 2, 7, 8, 10, 15 ];var b = [ 1, 6, 7, 8 ];var c = [ 4, 5, 5 ];var l1 = a.length;var l2 = b.length;var l3 = c.length;var x = 14;if (existsTriplet(a, b, c, x, l1, l2, l3)) document.write("Yes");else document.write("No");</script> |
Yes
Сложность времени: O (min (len (A), len (B), len (C)) * max (len (A), len (B), len (C)))
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.