راه حل 3Sum Leetcode  


سطح دشواری متوسط
اغلب در خشت آمازون سیب بلومبرگ فیس بوک گوگل مایکروسافت وحی تسلا آموزش VMware
الگوریتم صف برنامه نویسی مصاحبه مصاحبه آماده 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 (Brute Force + جستجوی دودویی)  

ما باید سه گانه منحصر به فرد با a + b + c = 0 پیدا کنیم ، فرض کنید ما مقدار a و b را می دانیم ، با استفاده از معادله (a + b + c = 0) می توانیم مقدار c را پیدا کنیم ، یعنی - ( a + b)

اگر همه جفت های ممکن (a ، b) را بگیریم ، می توانیم همه جفت های a ، b را با استفاده از 2 حلقه تو در تو بدست آوریم. پس از آن ، می توانیم از جستجوی دودویی استفاده کنیم تا بدانیم c = - (a + b) در آرایه داده شده وجود دارد یا خیر.
اگر وجود داشته باشد ، سه قلو (a ، b ، - (a + b)) یک سه قلو محتمل خواهد بود. به این ترتیب ، تمام سه قلوهای ممکن را با + b + c = 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

پیچیدگی زمان

O (N * N * log (N)): ما از دو حلقه تو در تو استفاده می کنیم تا تمام جفت ممکن (a، b) و جستجوی باینری را بفهمیم تا بفهمیم - (a + b) در آرایه وجود دارد یا خیر.

پیچیدگی فضا 

بر): ما برای بدست آوردن سه قلوهای منحصر به فرد از مجموعه ای استفاده می کنیم.

رویکرد 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

پیچیدگی زمان

O (N ^ 2): ما از یک حلقه برای بدست آوردن مقادیر a استفاده می کنیم و برای هر مقدار a ، جفت b ، c را پیدا می کنیم (به عنوان مثال a + b + c = 0) با استفاده از دو رویکرد اشاره گر که زمان O (N) می گیرد. بنابراین پیچیدگی کل زمان از درجه O است (N ^ 2).

همچنین مشاهده کنید
بهترین زمان برای خرید و فروش Stock II Leetcode Solution

پیچیدگی فضا 

بر): ما برای ذخیره پاسخ از بردار استفاده می کنیم.

1