বিভিন্ন তিনটি অ্যারে থেকে এমন তিনটি উপাদান খুঁজে নিন যেমন একটি + বি + সি = যোগফল


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ডেটাব্রিক্স ডাইরেক্টি জেপি মরগান ট্যাক্সি4 সুরক্ষা Twilio Zoho
বিন্যাস কাটা হ্যাশ

ইন্টারভিউয়ারদের কাছে থ্রি সম একটি সমস্যা পছন্দ করে। এটি এমন একটি সমস্যা যা আমাকে ব্যক্তিগতভাবে জিজ্ঞাসা করা হয়েছিল during মর্দানী স্ত্রীলোক সাক্ষাত্কার। সুতরাং, আর কোনও সময় নষ্ট না করে আসুন আমরা সমস্যায় ফেলি। ধনাত্মক এবং নেতিবাচক উভয় সংখ্যা রয়েছে এমন একটি অ্যারে। তিনটি সংখ্যা যা শূন্য / সমষ্টি পর্যন্ত সংশোধন করা যেতে পারে, কোনও পূর্ণসংখ্যার যোগফল যোগ করতে বা বিভিন্ন তিনটি অ্যারে থেকে যেমন + + বি + সি = যোগফলের ত্রি-উপাদান খুঁজে পাওয়া যায়।

উদাহরণ

ইনপুট

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

আউটপুট

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

কীভাবে সমাধান করবেন?

আমার পাঠকদের জন্য এটি আরও বড় কষ্ট হওয়ার আগে। আমি একই চিত্রিত ছোট সিউডোকোড মাধ্যমে চালানো যাক। ধাপে ধাপে:

  • প্রথমত সাজান সংখ্যা.
  • বাছাই করা তাদের দৈর্ঘ্য অনুযায়ী অঙ্কগুলিতে অ্যাক্সেস করতে সহায়তা করে।
  • দ্বিতীয়ত, আমরা অ্যারে থেকে একটি উপাদান নির্বাচন করি।
  • তৃতীয়ত আমরা দুটি উপাদান নির্বাচন করি যারা প্রথম উপাদানটির সাথে যোগফলগুলি শূন্যের ফলস্বরূপ।
  • আপনি যদি একটি Deja ভু হয়ে থাকেন তবে আমাকে একটি ইঙ্গিত ফেলতে দিন।
  • The Olymp Trade প্লার্টফর্মে ৩ টি উপায়ে প্রবেশ করা যায়। প্রথমত রয়েছে ওয়েব ভার্শন যাতে আপনি প্রধান ওয়েবসাইটের মাধ্যমে প্রবেশ করতে পারবেন। দ্বিতয়ত রয়েছে, উইন্ডোজ এবং ম্যাক উভয়ের জন্যেই ডেস্কটপ অ্যাপলিকেশন। এই অ্যাপটিতে রয়েছে অতিরিক্ত কিছু ফিচার যা আপনি ওয়েব ভার্শনে পাবেন না। এরপরে রয়েছে Olymp Trade এর এন্ড্রয়েড এবং অ্যাপল মোবাইল অ্যাপ। দুই সুম সমস্যা।
  • একবার যখন আমরা প্রথম উপাদানটি ঠিক করি তখন আমরা অন্য দুটি উপাদান খুঁজে বের করতে অ্যারের উপরে চলে যাই।
  • আমরা দুটি প্রান্ত নিতে।
  • প্রতিবার দুটি প্রান্ত থেকে যোগফলটি কাঙ্ক্ষিতের চেয়ে বৃহত্তর হয় আমরা শেষের মানটি হ্রাস করি।
  • প্রতিবার দুটি প্রান্ত থেকে যোগফল কাঙ্ক্ষিতের চেয়ে কম হয় আমরা প্রারম্ভিক মানটি বৃদ্ধি করি।
  • যোগফল 0 এ পৌঁছলে আমরা উপাদানগুলি রেকর্ড করি।
  • শেষ পর্যন্ত, যাতে কোনও পুনরাবৃত্তি না হয় তা নিশ্চিত করার জন্য উপাদানগুলিকে সেটটির একটি অ্যারেলিস্টে যুক্ত করা হয়।

তিন যোগের জন্য জাভা কোড

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);
    }
}

সি ++ থ্রি সমের জন্য কোড

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;
    }
};

জটিলতা বিশ্লেষণ

সময় জটিলতা = হে (n ^ 2)

স্পেস জটিলতা = হে (1)

কিভাবে?

তিনটি যোগফলের জন্য সময় জটিলতা বিশ্লেষণ

  • প্রথমত, আমরা ঠিক করতে পারি এমন প্রথম উপাদানটি খুঁজে বের করার পরে আমরা বাইরের লুপটি দিয়ে চলে যাই।
  • ভিতরের লুপ।
  • প্রথম উপাদান নেয়।
  • শেষ থেকে দ্বিতীয় উপাদান নেয়।
  • আরও খারাপ ক্ষেত্রে, আমরা প্রথম উপাদান থেকে শেষ উপাদানটিতে যেতে শুরু করব।
  • যা ও এর সময় জটিলতার দিকে নিয়ে যায় (n ^ 2)

তিন যোগফলের জন্য স্পেস জটিলতা বিশ্লেষণ

  • ট্র্যাক রাখতে আমরা কয়েকটি ভেরিয়েবল ব্যবহার করি।
  • সুতরাং, স্পেস জটিলতায় ও (1) এর দিকে নিয়ে যাওয়া

একটি ছোট ত্বক

আমরা যদি থ্রি সম সমস্যার সমস্যার সঞ্চয়স্থান ইউনিট পরিবর্তন করি তবে কী হবে। আশ্চর্য !?

বেশি কিছু না. আমরা কেবল একটির চেয়ে তিনটি আলাদা অ্যারে গ্রহণ করব। যদি আপনি এখনও এটি না পান। আমি একটি নমুনা পরীক্ষা কেস উপস্থাপন করা যাক।

ইনপুট

অ্যারে 1 = {1, 2, 3, 4, 5}

অ্যারে 2 = {2, 3, 6, 1, 2}

অ্যারে 3 = {3, 2, 4, 5, -6}

আউটপুট

হ্যাঁ

এখানে সম্ভাব্য ট্রিপলটি হাইলাইট করা একটি চিত্র is

তিন যোগ

কীভাবে সমস্যাটির কাছে আসা যায়

  • প্রথমত, আমরা কোনও দুটি অ্যারে থেকে যোগফলের সমস্ত সম্ভাব্য সংমিশ্রণ উত্পন্ন করার চেষ্টা করি।
  • এটি অর্জনের জন্য আমরা দুটি লুপ চালাই
  • পুনরাবৃত্তি এড়াতে আমরা এই সমস্ত সংমিশ্রণগুলিকে একটি সেটে সংরক্ষণ করি
  • যোগফলের-মানটি তৃতীয় অ্যারেতে পাওয়া যায় কিনা তা আমরা পরীক্ষা করি
  • যদি হ্যাঁ হয় তবে আমরা হ্যাঁ ফিরে আসি
  • সবশেষে সমস্ত অ্যারে লুপ করার পরেও যদি আমরা 0 অর্জন না করি তবে আমরা মিথ্যা প্রত্যাবর্তন করি

তিন যোগের জন্য জাভা কোড

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));
    } 
}

সি ++ থ্রি সমের জন্য কোড

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; 
}

জটিলতা বিশ্লেষণ

সময় জটিলতা = হে (n ^ 2)

কিভাবে?

  • দ্বিতীয় অ্যারে থেকে উপাদানটি খুঁজতে আমরা একটি বাহ্যিক লুপ চালাই run
  • অভ্যন্তরীণ লুপে আমরা তৃতীয় অ্যারে থেকে দ্বিতীয় অ্যারের উপাদানকে একটি উপাদান যুক্ত করি।
  • এখনও অবধি সময় জটিলতা হ'ল হে (এন ^ 2)।
  • পরবর্তী লুপটি প্রথম অ্যারে থেকে উপাদানটি পরীক্ষা করে
  • এই লুপের জন্য সময় জটিলতা = হে (1)
  • এখনও অবধি চূড়ান্ত জটিলতা = O (n ^ 2) + O (1) = O (n ^ 2)

স্পেস জটিলতা = ও (এন)

কিভাবে?

  • আমরা সমস্ত উপাদান সংরক্ষণ করার জন্য একটি সেট ব্যবহার করি
  • এটি ও (এন) এর সময়ের জটিলতায় বাড়ে