أوجد كل ثلاثة توائم بمجموع صفر  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون جنرال إلكتريك للرعاية الصحية جوجل رفع
مجموعة مزيج البحث فرز

توضح مشكلة "البحث عن جميع التوائم الثلاثة ذات المجموع الصفري" أنه يتم إعطاؤك مصفوفة تحتوي على عدد موجب وسالب. يطلب بيان المشكلة معرفة الثلاثي مع مجموع يساوي 0.

أوجد كل ثلاثة توائم بمجموع صفردبوس

مثال  

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

تفسير

هذه هي ثلاثة توائم مجموعها 0.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

تفسير

هذه هي الثلاثيات التي يكون مجموع الأعداد فيها 0 -5 + 2 + 3 = 0

خوارزمية  

  1. تصنيف حسب: المصفوفة المعطاة.
  2. تعيين منطقية متغير وجد إلى false.
  3. التكرار من i = 0 إلى i
    1. ضبط التنوب = أنا + 1 ، ثانية = ن -1 ومتغير آخر x إلى عنصر المصفوفة الحالي.
    2. بينما التنوب
      1. تحقق مما إذا كانت ثلاثة من العناصر معًا تشكل مجموع 0.
        1. إذا كان هذا صحيحًا ، فقم بطباعة جميع الأرقام الثلاثة وضبطها على صحيح.
      2. تحقق مما إذا كان مجموع العناصر الثلاثة (عناصر المصفوفة الحالية) أقل من 0.
        1. إذا كان هذا صحيحًا ، فقم بزيادة قيمة التنوب بمقدار 1.
      3. تحقق مما إذا كان مجموع العناصر الثلاثة أكبر من 0.
          1. إذا كان هذا صحيحًا ، فقم بتقليل قيمة sec بمقدار 1.
  4. تحقق مما إذا كان تم العثور على خطأ ، فهذا يعني أنه لا يمكن تكوين ثلاثة توائم.

تفسير

لقد حصلنا على مجموعة. ثم يطلب منا تحديد الثلاثيات التي يمكن تشكيلها بالأرقام المحددة في مصفوفة مجموعها 0. سنستخدم حلقة متداخلة. يمكن أن تعمل هذه الخوارزمية في مساحة ثابتة. أولاً ، سنقوم بفرز المصفوفة. بهذه الطريقة يمكننا استخدام تقنية المؤشر الثنائي. سنعلن عن متغير منطقي واحد ونضبط قيمته على خطأ في البداية. هذا فقط للتأكد من أننا لم نعثر على أي من الثلاثيات التي تحتوي على عناصر مجموعها 0 ، قيمة وجد يبقى أن يكون خطأ. ثم سنقوم بتحديثه إلى صحيح كلما وجدنا ثلاثة توائم. وبهذا ، يمكننا أن نستنتج أنه لم يتم العثور على ثلاثة توائم.

انظر أيضا
احذف واكسب

سنقوم بفرز المصفوفة أولاً ، في الحلقة المتداخلة. ثم نجتاز المصفوفة حتى n-1. سنقوم بتعيين قيمة البداية على أنها i + 1 ، والقيمة الأخيرة على n-1 ، وقيمة x على القيمة الحالية في الحلقة الخارجية. في الحلقة الداخلية سنجتاز قيم المصفوفة ، ونتحقق مما إذا كان مجموع العناصر الثلاثة (x + arr [fir] + arr [sec]) يساوي 0 أم لا. إذا تم العثور على 0 ، فهذا يعني أننا وجدنا الزوج الأول وطبعنا جميع القيم الحالية للمصفوفة ، وقمنا بتعيين قيمة isFound على true.

يشير هذا إلى أننا وجدنا أحد الأزواج. إذا كان مجموع ثلاثة توائم لا يساوي 0. نتحقق مما إذا كان مجموع العناصر الثلاثة الحالية أقل من 0. إذا كان المجموع أقل من 0. نحن نزيد التنوب ، فهذا يعني أن قيمة البداية لدينا زادت. إذا لم يتم استيفاء الحالة. نتحقق مما إذا كان المجموع أكبر من 0. إذا كان صحيحًا ، فقم بالتناقص ثانية.

بهذه الطريقة ، سنجد كل التوائم الثلاثة الممكنة التي يمكن أن يكون مجموعها 0.

كود C ++ للبحث عن كل ثلاثة توائم بمجموع صفر  

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

كود جافا للبحث عن كل ثلاثة توائم بمجموع صفر  

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

تحليل التعقيد  

تعقيد الوقت

على2) أين "ن"  هو عدد العناصر في المصفوفة. نظرًا لأننا نستخدم أسلوبين للمؤشر يساهمان في وقت O (n). لكن هذه التقنية نفسها تستخدم لوقت O (n). وبالتالي ، يتم تشغيل الخوارزمية في وقت O (n ^ 2).

انظر أيضا
3 سوم

تعقيد الفضاء

يا (1) حيث لا توجد مساحة إضافية مطلوبة.