वेगळ्या तीन अ‍ॅरेमधून तीन घटक शोधा जसे की + बी + सी = बेरीज


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन डेटाबे्रिक्स डायरेक्टि जेपी मॉर्गन टॅक्सी 4 सुअर Twilio Zoho
अरे हॅश हॅशिंग

तीन सम ही मुलाखत घेणार्‍याना आवडणारी एक समस्या आहे. दरम्यान मला वैयक्तिकरित्या विचारले गेले होते ही एक समस्या आहे ऍमेझॉन मुलाखत. म्हणून, आणखी वेळ न घालवता समस्या येऊ द्या. अ‍ॅरे ज्यात सकारात्मक आणि नकारात्मक दोन्ही आहेत. शून्य / बेरीज होणार्‍या तीन संख्यांमधील बदल, कोणत्याही पूर्णांकाची बेरीज करण्यासाठी किंवा a + b + c = बेरीज सारख्या भिन्न तीन अ‍ॅरेमधून तीन-घटक शोधू शकता.

उदाहरण

इनपुट

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

उत्पादन

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

ते कसे सोडवायचे?

माझ्या वाचकांसाठी ती मोठी वेदना होण्यापूर्वी. मी हेच दाखवून देत छोट्या छोट्या स्यूडोकोडमधून जाऊ. क्रमाक्रमाने:

  • पहिल्याने क्रमवारी संख्या.
  • क्रमवारी लावण्यामुळे आम्हाला त्यांच्या विशालतेनुसार अंकांमध्ये प्रवेश करण्यात मदत होते.
  • दुसरे म्हणजे, आपण अ‍ॅरेमधून एक घटक निवडतो.
  • तिसर्यांदा आम्ही दोन घटक निवडतो जे पहिल्या घटकासह एकत्रितपणे शून्य मिळतील.
  • जर तुमच्याकडे देजा व्ही येत असेल तर मला एक इशारा सोडा.
  • अगोदर निर्देश केलेल्या बाबीसंबंधी बोलताना दोन SUM समस्या.
  • एकदा आम्ही पहिला घटक निश्चित केला की आम्ही इतर दोन घटक शोधण्यासाठी अ‍ॅरेवरुन धावतो.
  • आम्ही दोन टोक घेतो.
  • प्रत्येक वेळी जेव्हा दोन टोकांची बेरीज अपेक्षेपेक्षा जास्त असते तेव्हा आम्ही शेवटचे मूल्य कमी करतो.
  • प्रत्येक वेळी जेव्हा दोन टोकांची बेरीज अपेक्षेपेक्षा कमी असते तेव्हा आम्ही प्रारंभ मूल्य वाढवितो.
  • जर बेरीज 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;
    }
};

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी = ओ (एन ^ 2)

स्पेस कॉम्प्लेक्सिटी = ओ (1)

कसे?

तीन बेरीजसाठी वेळ कॉम्प्लेक्सिटी विश्लेषण

  • प्रथम आम्ही एकदा निराकरण करू शकणारा पहिला घटक शोधल्यानंतर आम्ही बाह्य पळवाट पार करतो.
  • आतील पळवाट.
  • प्रथम घटक घेते.
  • शेवटपासून दुसरा घटक घेते.
  • सर्वात वाईट परिस्थितीत, आम्ही कदाचित पहिल्या घटकापासून शेवटच्या घटकाकडे जाण्यास सुरवात करू.
  • जे ओ च्या वेळेची गुंतागुंत ठरवते (n ^ 2)

तीन बेरीजसाठी स्पेस कॉम्प्लेक्सिटी विश्लेषण

  • आम्ही ट्रॅक ठेवण्यासाठी फक्त काही चल वापरतो.
  • अशा प्रकारे, ओ (1) मधील अवकाशातील अवघडपणा

एक छोटा चिमटा

जर आम्ही थ्री सम समस्येचे स्टोरेज युनिट बदलले तर काय होईल. आश्चर्यचकित !?

खास काही नाही. आम्ही एकापेक्षा तीन भिन्न अ‍ॅरे घेऊ. जर आपणास अद्याप मिळाला नाही. मी एक नमुना चाचणी प्रकरण सादर करू.

इनपुट

अ‍ॅरे 1 = {1, 2, 3, 4, 5}

अ‍ॅरे 2 = {2, 3, 6, 1, 2}

अ‍ॅरे 3 = {3, 2, 4, 5, -6}

उत्पादन

होय

येथे संभाव्य तिप्पटांवर प्रकाश टाकणारी एक प्रतिमा आहे

तीन बेरीज

समस्येकडे कसे जायचे

  • प्रथम, आम्ही कोणत्याही दोन अ‍ॅरेमधून बेरीजची सर्व संभाव्य जोड व्युत्पन्न करण्याचा प्रयत्न करतो.
  • हे साध्य करण्यासाठी आम्ही दोन लूप चालवितो
  • पुनरावृत्ती टाळण्यासाठी आम्ही या सर्व जोड्या एका संचात संचयित करतो
  • बेरीजचे-मूल्य मूल्य तिसर्‍या अ‍ॅरेमध्ये उपलब्ध आहे का ते आम्ही तपासतो
  • असल्यास होय आम्ही होय परत करतो
  • शेवटी सर्व अ‍ॅरे लूप करूनही जर आपण 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; 
}

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी = ओ (एन ^ 2)

कसे?

  • दुसर्‍या अ‍ॅरेमधून घटक शोधण्यासाठी आम्ही बाह्य पळवाट चालवितो.
  • अंतर्गत लूपमध्ये आम्ही तिसर्‍या अ‍ॅरेपासून दुसर्‍या अ‍ॅरे घटकात घटक समाविष्ट करतो.
  • आतापर्यंत झालेली वेळ गुंतागुंत ओ (एन ^ 2) आहे.
  • पुढील लूप पहिल्या अ‍ॅरेमधून घटक तपासते
  • या पळवाट साठी वेळ गुंतागुंत = ओ (1)
  • आतापर्यंतची अंतिम गुंतागुंत = ओ (एन ^ 2) + ओ (1) = ओ (एन ^ 2)

स्पेस कॉम्प्लेक्सिटी = ओ (एन)

कसे?

  • आम्ही सर्व घटक संग्रहित करण्यासाठी एक सेट वापरतो
  • हे ओ (एन) च्या वेळेची गुंतागुंत निर्माण करते