3 সুম লেটকোড সমাধান


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ফেসবুক গুগল মাইক্রোসফট আকাশবাণী টেসলা অথবা VMware
বিন্যাস দুই পয়েন্টার

সমস্যা বিবৃতি

দেওয়া হয়েছে একটি বিন্যাস 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) আমরা সিটির মান খুঁজে পেতে পারি, যা হ'ল - ( ক + খ)।

যদি আমরা সমস্ত সম্ভাব্য (ক, খ) জোড়া নিই, তবে লুপগুলির জন্য 2 টি নেস্টেড ব্যবহার করে আমরা a, b এর সমস্ত জোড়া পেতে পারি। এর পরে, আমরা বাইনারি অনুসন্ধান ব্যবহার করতে পারি যে প্রদত্ত অ্যারেতে সি = - (এ + বি) বিদ্যমান আছে কিনা।
যদি এটি বিদ্যমান থাকে তবে ট্রিপলেট (a, b, - (a + b)) একটি সম্ভাব্য ট্রিপলেট হবে। এইভাবে, আমরা একটি + বি + সি = 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

3 সুম লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এন * লগ (এন)): আমরা লুপগুলির জন্য দুটি সম্ভাব্য (ক, খ) জুড়ি এবং একটি বাইনারি অনুসন্ধান পেতে - (এ + বি) অ্যারেটিতে উপস্থিত রয়েছে কিনা তা জানতে দুটি নেস্ট ব্যবহার করছি।

স্পেস জটিলতা ity 

চালু): আমরা অনন্য ট্রিপল্ট পেতে একটি সেট ব্যবহার করছি।

অ্যাপ্রোচ 2 (দুই পয়েন্টার)

একই কাজটি করার জন্য আরও ভাল পন্থা হল দুটি পয়েন্টার, মূল ধারণাটি হ'ল আমরা একটি নির্বাচন করি এবং তারপরে বি এবং সি অনুসন্ধান করতে দুটি পয়েন্টার ব্যবহার করি যাতে একটি + বি + সি = 0 হয়।
আমাদের দুটি পয়েন্টার এমনভাবে সরানো দরকার যে আমরা বি + সি = এ পাই।
কৃপণ বাস্তবায়ন ব্যবহার করে আমরা সেট ব্যবহার এড়াতে পারি (যা অনন্য পাওয়ার জন্য ব্যবহৃত হয়েছিল)
পদ্ধতির ট্রিপল্ট 1)

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

3 সুম লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2): আমরা একটি এর মান পেতে লুপগুলির জন্য একটি ব্যবহার করি এবং এর প্রতিটি মানের জন্য আমরা ও (এন) সময় লাগে এমন দুটি পয়েন্টার পদ্ধতির সাহায্যে জোড় বি, সি (যেমন একটি + বি + সি = 0) পাই find সুতরাং মোট সময়ের জটিলতা হ'ল অর্ডার (এন ^ 2)।

স্পেস জটিলতা ity 

চালু): আমরা উত্তরটি সঞ্চয় করতে ভেক্টর ব্যবহার করছি are