מצא שלישייה במערך עם סכום נתון  


רמת קושי בינוני
נשאל לעתים קרובות נאמן Adobe אמזון בעברית תפוח עץ בלומברג Byte סיסקו מצודה Citrix דלתא eBay פייסבוק גולדמן זאקס Google Hulu יבמ אינפוסיס עבודות מתמטיקה מיקרוסופט מורגן סטנלי אורקל פייפאל Qualtrics סמסונג ServiceNow מתיז בצורת ריבוע Tencent טסלה סופר וִיזָה VMware מעבדות וולמארט יאהו Zoho
Akamai מערך CarWale Groupon פוסטרים יישומי עבודות

הצהרת בעיה  

בהינתן מערך של מספרים שלמים, מצא את השילוב של שלושה אלמנטים ב מערך שסכומם שווה לערך נתון X. כאן נדפיס את הצירוף הראשון שנקבל. אם אין שילוב כזה, הדפס -1.

דוגמה  

קֶלֶט

N = 5, X = 15

arr [] = {10, 4, 2, 3, 5}

תְפוּקָה 

10, 2, 3

גישה 1  

יצירת כל השלישיות והשוואת הסכום לערך הנתון. האלגוריתם שלהלן מכיל שלוש לולאות.

אַלגוֹרִיתְם

  1. ראשית ממיין את מערך הקלט
  2. תקן את האלמנט הראשון כ- arr [i], כאשר אני נע בין 0 ל- N-2.
  3. לאחר תיקון האלמנט הראשון, תקן את האלמנט השני כ arr [j], כאשר j נע בין i + 1 ל- N-1.
  4. לאחר תיקון האלמנט השני, תקנו את האלמנט השלישי כ- arr [k], כאשר k נע בין j + 1 ל- N.
  5. מצא את הסכום, arr [i] + arr [j] + arr [k].
  6. אם סכום השלישיות שווה לערך X, הדפיסו את שלושת האלמנטים האחרים - -1.

יישום

תוכנית C ++ למציאת שלישייה במערך עם סכום נתון

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

תוכנית Java לחיפוש שלישייה במערך עם סכום נתון

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if( a[i] + a[j] + a[k] == x)
                    {
                       System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                       i=n;j=n;k=n;
                       temp=1;
                    }
                }
            }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
10 4 2 3 5
10  2  3

ניתוח מורכבות

מורכבות זמן

O (n * n * n) איפה n הוא מספר האלמנטים הקיימים במערך. כאן אנחנו רון שלוש עבור לולאה ובודקים אם כל שלישייה אפשרית.

ראה גם
נחש את המילה

מורכבות בחלל

O (1) כי אנחנו לא משתמשים בשום שטח עזר כאן.

גישה 2  

אַלגוֹרִיתְם

  1. ראשון sort מערך הקלט
  2. תקן את האלמנט הראשון כ- arr [i], כאשר אני נע בין 0 ל- N-2.
  3. לאחר תיקון האלמנט הראשון, למציאת שני האלמנטים הבאים, קח משתנים דמויי שני מצביעים (j = i + 1, k = N-1) וחצה את האלגוריתם למציאת הסכום במערך ממוין.
  4. בעוד ש- j הוא פחות מ- k הוסף את האלמנטים באינדקסים הנתונים כלומר arr [i] + arr [j] + arr [k] אם סכום שלישייה שווה לערך X, הדפס את שלושת האלמנטים האחרים אם סכום שלישייה קטן מ הערך X, ואז הגדל את ערך j אחרת הקטין את הערך של k.

יישום

תוכנית C ++ למציאת שלישייה במערך עם סכום נתון

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}

תוכנית Java לחיפוש שלישייה במערך עם סכום נתון

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); //sort the array in ascending order
        int computed_sum;//sum computed at each step
        int temp=0;
        for(int i = 0; i < n - 2; i++) // fix one element and search for other two elements in linear time
        {
          int j = i+1 , k = n-1; // jth index starts from the next element of selected and k always starts at the ending index
          while(j < k)
          {
            computed_sum = a[i] + a[j] + a[k]; // add the elements at the given indices
            if(computed_sum == x)
              {
                System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                j=k;
                temp=1;
              }
            else if(computed_sum < x) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
              j++;
            else if(computed_sum > x)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
              k--;
          }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
1 4 2 3 5
-1

ניתוח מורכבות

מורכבות זמן

O (n * n * n) איפה n הוא מספר האלמנטים הקיימים במערך. כאן אנחנו רון שלוש עבור לולאה ובודקים אם כל שלישייה אפשרית.

ראה גם
הדפיסו את כל השלישיות במערך ממוין היוצרות AP

מורכבות בחלל

O (1) כי אנחנו לא משתמשים בשום שטח עזר כאן.

הפניות