3 سم لیٹ کوڈ حل  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ فیس بک گوگل مائیکروسافٹ اوریکل Tesla VMware
یلگوردمز لڑی کوڈنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔ دو پوائنٹر

مسئلہ یہ بیان  

ایک دیا صف (n) انٹیجرز کے ، کیا عدد میں ایک ، بی ، سی عنصر ایسے ہیں کہ ایک + بی + سی = 0؟ صف میں تمام انوکھا ٹرپلٹس تلاش کریں جو صفر کا مجموعہ دیتا ہے۔
نوٹس: کہ حل سیٹ میں ڈپلیکیٹ ٹرپلٹس نہیں ہونا چاہئے۔

مثال کے طور پر

#1

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

وضاحت:3 سم لیٹ کوڈ حل

#2

[0]
[]

 

نقطہ نظر 1 (بروٹ فورس + بائنری تلاش)  

ہمیں a + b + c = 0 کے ساتھ انوکھا ٹرپلٹ ڈھونڈنے کی ضرورت ہے ، آئیے یہ کہتے ہیں کہ ہم a اور b کی قدر جانتے ہیں ، مساوات (a + b + c = 0) کا استعمال کرتے ہوئے ہمیں c کی قدر مل سکتی ہے ، جو ہے - a + b)۔

اگر ہم تمام ممکنہ (ا ، بی) جوڑے لیتے ہیں تو ، ہم لوپوں کے لئے 2 گھونسلے کا استعمال کرتے ہوئے ، a ، b کے تمام جوڑے حاصل کرسکتے ہیں۔ اس کے بعد ، ہم یہ جاننے کے لئے بائنری تلاش کا استعمال کرسکتے ہیں کہ آیا دیئے گئے صف میں سی = - (ایک + بی) موجود ہے یا نہیں۔
اگر یہ موجود ہے تو پھر سہ رخی (a، b، - (a + b)) ایک ممکنہ سہ رخی ہوگی۔ اس طرح ، ہمیں a + b + c = 0 کے ساتھ ہر ممکن ٹرپلٹس ملیں گے ، لیکن ہمیں انوکھے تین چہرے تلاش کرنے کی ضرورت ہے ،
اس کے لئے ہم ان تمام ممکنہ ٹرپلٹس کو کچھ اعداد و شمار کے ڈھانچے (جیسے سیٹ) میں داخل کرسکتے ہیں تاکہ منفرد ٹرپلٹس حاصل کیے جاسکیں۔

3 سوم لیٹکوڈ حل کے لئے عمل درآمد

سی ++ پروگرام

#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 * لاگ (N)): ہم دو ممکنہ (ا ، بی) جوڑی اور بائنری تلاش کرنے کے لئے دو گھونسلے استعمال کر رہے ہیں تاکہ یہ معلوم ہو سکے کہ - (a + b) صف میں موجود ہے یا نہیں۔

خلائی پیچیدگی 

O (N): ہم ایک منفرد سیٹ کو حاصل کرنے کیلئے سیٹ استعمال کررہے ہیں۔

نقطہ نظر 2 (دو پوائنٹر)  

ایک ہی کام کے ل A بہتر نقطہ نظر دو پوائنٹرز ہیں ، بنیادی خیال یہ ہے کہ ہم نے ایک کو منتخب کیا ہے اور پھر b اور c تلاش کرنے کے ل two دو پوائنٹرز کا استعمال کرتے ہیں جیسے ایک + b + c = 0۔
ہمیں دو پوائنٹرز کو اس طرح منتقل کرنے کی ضرورت ہے کہ ہمیں b + c = a مل جائے۔
مشکل نفاذ کا استعمال کرتے ہوئے ہم سیٹ کے استعمال سے بچ سکتے ہیں (جو منفرد ہونے کے لئے استعمال کیا جاتا تھا
نقطہ نظر میں تینوں)

3 سوم لیٹکوڈ حل کے لئے عمل درآمد

سی ++ پروگرام

#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): ہم ایک کی قدریں حاصل کرنے کے لئے لوپ کے لئے ایک استعمال کررہے ہیں ، اور ایک کی ہر قیمت کے ل we ، ہمیں جوڑا ب ، سی (جیسے کہ + + + + = =) دو پوائنٹر نقطہ نظر کا استعمال کرتے ہوئے پاتے ہیں جس میں او (این) وقت لگتا ہے۔ لہذا کل وقتی پیچیدگی O (N ^ 0) کے ترتیب کی ہے۔

یہ بھی دیکھتے ہیں
اسٹاک II لیٹکوڈ حل خریدنے اور بیچنے کا بہترین وقت

خلائی پیچیدگی 

O (N): ہم جواب ذخیرہ کرنے کے لئے ایک ویکٹر کا استعمال کررہے ہیں۔