3Sum Leetcode الحل  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ Facebook جوجل Microsoft أوراكل تسلا في إم وير
خوارزميات مجموعة الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions مؤشر اثنين

المشكلة بيان  

نظرا ل مجموعة من الأعداد الصحيحة n ، هل توجد العناصر a و b و c بالأرقام بحيث يكون a + b + c = 0؟ ابحث عن جميع التوائم الثلاثة الفريدة في المصفوفة التي تعطي مجموع الصفر.
ملاحظة: يجب ألا تحتوي مجموعة الحلول على ثلاثة توائم مكررة.

مثال

#1

[-1,0,1,2,-1,4]
[[-1,0,1],[-1,-1,2]]

التفسير:3Sum Leetcode الحل

#2

[0]
[]

 

النهج 1 (القوة الغاشمة + بحث ثنائي)  

نحتاج إلى إيجاد ثلاثة توائم فريدة مع أ + ب + ج = 0 ، دعنا نقول أننا نعرف قيمة أ وب ، باستخدام المعادلة (أ + ب + ج = 0) يمكننا إيجاد قيمة ج ، وهي - ( أ + ب).

إذا أخذنا كل الأزواج الممكنة (أ ، ب) ، فيمكننا الحصول على كل أزواج من a ، b باستخدام حلقتين متداخلتين for. بعد ذلك ، يمكننا استخدام البحث الثنائي لمعرفة ما إذا كان c = - (a + b) موجودًا في المصفوفة المحددة أم لا.
إذا كان موجودًا ، فسيكون الثلاثي (أ ، ب ، - (أ + ب)) ثلاثيًا محتملاً. بهذه الطريقة ، نحصل على جميع التوائم الثلاثة الممكنة مع أ + ب + ج = 0 ، لكننا بحاجة إلى إيجاد التوائم الثلاثة الفريدة ،
لذلك يمكننا إدخال كل هذه الثلاثة توائم الممكنة في بعض هياكل البيانات (أي مجموعة) للحصول على ثلاثة توائم فريدة.

تنفيذ حل 3Sum Leetcode

برنامج C ++

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s;//to get unique triplets
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> temp;
        temp.resize(3);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(nums.begin()+j+1,nums.end(),-nums[i]-nums[j])){
                     temp[0]=nums[i],temp[1]=nums[j],temp[2]=-nums[i]-nums[j];
                    sort(temp.begin(),temp.end());
                    //to get triplet in an order, will be easy to check if 
                    //duplicate exists or not
                    s.insert(temp);
                    }
            }
        vector<vector<int>> ans;
        for(auto triplet: s)
            ans.push_back(triplet);
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

برنامج جافا

import java.util.*;
class Rextester{
    
  static boolean binary_search(int l,int r,int[]nums, int x)
    {
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(nums[mid]==x) return true;
            else if(nums[mid]>x) r=mid-1;
            else l=mid+1;
        }
        return false;
    }
    
    public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(j+1,n-1,nums,-(nums[i]+nums[j])))
                {
                    List<Integer> t=new  ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(-(nums[i]+nums[j]));
                    ans.add(t);
                }
                
                while(j+1<n && nums[j+1]==nums[j]) j++;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        
        return ans;  
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

تحليل التعقيد لحل 3Sum Leetcode

تعقيد الوقت

O (N * N * log (N)): نحن نستخدم حلقتين متداخلتين للحصول على كل الأزواج (أ ، ب) الممكنة وبحث ثنائي لمعرفة ما إذا كان - (أ + ب) موجودًا في المصفوفة أم لا.

تعقيد الفضاء 

على): نحن نستخدم مجموعة للحصول على ثلاثة توائم فريدة.

النهج 2 (مؤشران)  

الطريقة الأفضل للقيام بالمهمة نفسها هي مؤشرين ، والفكرة الأساسية هي أن نختار a ثم نستخدم مؤشرين للعثور على b و c بحيث يكون a + b + c = 0.
نحتاج إلى تحريك المؤشرين بحيث نحصل على b + c = a.
باستخدام التنفيذ الصعب ، يمكننا تجنب استخدام المجموعة (التي تم استخدامها للحصول على فريدة
ثلاثة توائم في النهج 1)

تنفيذ حل 3Sum Leetcode

برنامج C ++

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
       vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n; i++)
        {
            int j=i+1,k=n-1;//two pointers
            while(j<n && j<k)
            {
                if(nums[j]+nums[k] == -nums[i])
                {
                    ans.push_back({nums[i],nums[j],nums[k]});
                    while(k!=0 && nums[k]==nums[k-1]) k--;//to avoid duplicates 
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++,k--;
                }
                else if(nums[j]+nums[k] > -nums[i]) 
                {
                    while(k!=0 && nums[k]==nums[k-1]) k--;
                    k--;
                }
                else
                {
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++;
                }
            }
            while(i!=n-1 && nums[i]==nums[i+1]) i++;
        }
        for(auto triplet : ans)
            sort(triplet.begin(),triplet.end());
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

برنامج جافا

import java.util.*;

class Rextester{
    
  public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        
        for(int i=0;i<n;i++)
        {
            int p=i+1,q=n-1;
            while(p<q)
            {
                if(nums[p]+nums[q]==-nums[i])
                { //System.out.println(p+" "+q);
                    List<Integer> t=new ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[p]);
                    t.add(nums[q]);
                 
                 ans.add(t);
                    
                    while(p+1<q &&  nums[p+1]==nums[p]) p++;
                    while(q-1>p &&  nums[q-1]==nums[q]) q--;
                    
                    p++; q--;
                }
                else if(nums[p]+nums[q] < -nums[i]) p++;
                else q--;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        return ans;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

تحليل التعقيد لحل 3Sum Leetcode

تعقيد الوقت

O (N ^ 2): نحن نستخدم حلقة for للحصول على قيم a ، ولكل قيمة من a ، نجد الزوج b ، c (بحيث أن a + b + c = 0) باستخدام نهج مؤشرين يستغرق وقت O (N). لذا فإن التعقيد الزمني الإجمالي هو من أجل O (N ^ 2).

انظر أيضا
أفضل وقت لشراء وبيع الأسهم II Leetcode Solution

تعقيد الفضاء 

على): نحن نستخدم متجه لتخزين الإجابة.