أوجد ثلاثة عناصر من ثلاث مصفوفات مختلفة بحيث يكون a + b + c = sum


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Databricks Directi JP مورغان تاكسي فور Twilio زوهو
مجموعة مزيج تجزئة

Three Sum هي مشكلة يحبها المحاورون. إنها مشكلة سُئلت شخصيًا خلال أمازون مقابلة. لذا ، دون إضاعة المزيد من الوقت ، دعونا نصل إلى المشكلة. مصفوفة تحتوي على أرقام موجبة وسالبة. ثلاثة أرقام مجموعها صفر / يمكن تعديلها ، لتلخيص أي عدد صحيح أو إيجاد ثلاثة عناصر من ثلاث مصفوفات مختلفة مثل a + b + c = sum.

مثال

إدخال

[-2,0,1,1,2،XNUMX،XNUMX،XNUMX،XNUMX]

الناتج

[[-2,0,2،2,1,1،XNUMX] ، [- XNUMX،XNUMX،XNUMX]]

كيفية حل هذه المشكلة؟

قبل أن يصبح الألم أكبر لقرائي. اسمحوا لي أن أجري عبر الشفرة الزائفة الصغيرة التي توضح الشيء نفسه. خطوة بخطوة:

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

كود جافا لثلاثة مجموع

class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        Arrays.sort(nums);
        if(nums.length<3)
            return new ArrayList<>();
        Set<List<Integer>>lisa=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            int start=i+1;
            int end=nums.length-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    List<Integer>cur=new ArrayList<Integer>();
                    cur.add(nums[i]);
                    cur.add(nums[start]);
                    cur.add(nums[end]);
                    lisa.add(cur);
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        return new ArrayList<>(lisa);
    }
}

كود C ++ لثلاثة مجموع

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        set<vector<int>>lisa;
        for(int i=0;i<nums.size();i++)
        {
            int start=i+1;
            int end=nums.size()-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    lisa.insert({nums[i],nums[start],nums[end]}); 
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        for(auto x:lisa)
        {
            ans.push_back(x);
        }
        return ans;
    }
};

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

تعقيد الوقت = O (ن ^ 2)

تعقيد الفضاء = O (1)

كيف؟

تحليل تعقيد الوقت لثلاثة مجموع

  • أولاً ، نجري عبر الحلقة الخارجية بمجرد إيجاد العنصر الأول الذي يمكننا إصلاحه.
  • الحلقة الداخلية.
  • يأخذ العنصر الأول.
  • يأخذ العنصر الثاني من النهاية.
  • في الحالة الأسوأ ، قد نبدأ في الانتقال من العنصر الأول إلى العنصر الأخير.
  • مما يؤدي إلى التعقيد الزمني لـ O (n ^ 2)

تحليل تعقيد الفضاء لثلاثة مجموع

  • نحن نستخدم فقط بعض المتغيرات لتتبعها.
  • وبالتالي ، يؤدي تعقيد الفضاء إلى O (1)

قرص صغير

ماذا لو قمنا بتغيير وحدات تخزين مشكلة الثلاثة مجموع. مندهش!؟

لا شىء اكثر. سنأخذ ثلاث مصفوفات مختلفة عن واحدة. في حالة ما زلت لم تحصل عليه. اسمحوا لي أن أقدم عينة من حالة الاختبار.

إدخال

صفيف 1 = {1، 2، 3، 4، 5}

صفيف 2 = {2، 3، 6، 1، 2}

صفيف 3 = {3، 2، 4، 5، -6}

الناتج

نعم

هذه صورة تسلط الضوء على الثلاثة توائم الممكنة

ثلاثة مجموع

كيف تقترب من المشكلة

  • أولاً ، نحاول إنشاء جميع التركيبات الممكنة للمجموع من أي مصفوفتين.
  • لتحقيق ذلك نقوم بتشغيل حلقتين
  • نقوم بتخزين كل هذه المجموعات في مجموعة لتجنب التكرار
  • نتحقق مما إذا كانت القيمة -ve للمجموع متاحة في المصفوفة الثالثة
  • إذا كانت الإجابة بنعم ، فنعود بنعم
  • أخيرًا ، حتى بعد المرور عبر جميع المصفوفات إذا لم نحقق 0 ، فإننا نعيد القيمة false

كود جافا لثلاثة مجموع

public class Main
{
    public static boolean Three(int a1[],int a2[],int a3[])
    {
        Set<Integer>store=new HashSet<Integer>();
        Set<ArrayList<Integer>>lisa=new HashSet<>();
        for(int i=0;i<a2.length;i++)
        {
            for(int j=0;j<a3.length;j++)
                store.add(a2[i]+a3[j]);
        }
        for(int i=0;i<a1.length;i++)
        {
            if(store.contains(-a1[i]))
            {
                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 n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
          
        System.out.println(Three(a1, a2, a3));
    } 
}

كود C ++ لثلاثة مجموع

bool Three(int a1[],int a2[],int a3[])
    {
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    set<int>store;
    for(int i=0;i<n2;i++)
    {
        for(int j=0;j<n3;j++)
            store.insert(a2[i]+a3[j]);
    }
    for(int i=0;i<n1;i++)
    {
        if(store.find(-a1[i])!=store.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 }; 
    cout<<Three(a1, a2, a3);
  
    return 0; 
}

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

تعقيد الوقت = O (ن ^ 2)

كيف؟

  • نقوم بتشغيل حلقة خارجية لإيجاد العنصر من المصفوفة الثانية.
  • في الحلقة الداخلية ، نضيف عنصرًا من المصفوفة الثالثة إلى عنصر المصفوفة الثاني.
  • التعقيد الزمني المتكبّد حتى الآن هو O (n ^ 2).
  • الحلقة التالية تتحقق من عنصر من المصفوفة الأولى
  • التعقيد الزمني لهذه الحلقة = O (1)
  • التعقيد النهائي حتى الآن = O (n ^ 2) + O (1) = O (n ^ 2)

تعقيد الفضاء = O (n)

كيف؟

  • نستخدم مجموعة لتخزين جميع العناصر
  • هذا يؤدي إلى تعقيد الوقت O (n)