مختلف تین صفوں میں سے تین عنصر تلاش کریں جس میں ایک + b + c = رقم ہے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ڈیٹا بکس ہدایت جے پی مورگن ٹیکسی 4 سوری Twilio Zoho
لڑی ہیش ہیکنگ

تھری سم ایک ایسا مسئلہ ہے جو انٹرویو لینے والوں کے ذریعہ پسند کیا جاتا ہے۔ یہ ایک مسئلہ ہے جس کے دوران مجھ سے ذاتی طور پر پوچھا گیا تھا ایمیزون انٹرویو. لہذا ، مزید وقت ضائع کیے بغیر ہمیں پریشانی کا سامنا کرنا چاہئے۔ ایک ایسی صف جس میں مثبت اور منفی دونوں نمبر ہیں۔ تین اعداد جن کی تعداد صفر ہے / اس میں ترمیم کی جاسکتی ہے ، کسی بھی عدد تک کا خلاصہ ہوسکتی ہے یا مختلف تین صفوں سے تین عنصر ڈھونڈ سکتی ہے جیسے ایک + بی + سی = جوہر۔

مثال کے طور پر

ان پٹ

[-2,0,1,1,2،XNUMX،XNUMX،XNUMX،XNUMX]

آؤٹ پٹ

[[-2,0,2،2,1,1،XNUMX]، [- XNUMX،XNUMX،XNUMX]]

اسے کیسے حل کریں؟

اس سے پہلے کہ یہ میرے پڑھنے والوں کے لئے ایک بڑا تکلیف بن جائے۔ مجھے ایک ہی مثال دیتے ہوئے چھوٹے سیڈوکوڈ کے ذریعے چلنے دو۔ قدم بہ قدم:

  • اول ترتیب دیں نمبر
  • ترتیب دینے سے ہمیں ہندسوں تک ان کی وسعت کے مطابق رسائی حاصل کرنے میں مدد ملتی ہے۔
  • دوم ، ہم صف سے ایک عنصر منتخب کرتے ہیں۔
  • تیسری بات یہ ہے کہ ہم دو عنصر منتخب کرتے ہیں جو پہلے عنصر کے ساتھ جوڑ کر صفر حاصل کریں گے۔
  • اگر آپ کو ڈیجا وو ہو رہا ہے تو مجھے ایک اشارہ چھوڑنے دو۔
  • ۔ ٹی وی 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);
    }
}

C ++ کوڈ کے لئے تین کا حساب

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی = O (n ^ 2)

خلائی پیچیدگی = O (1)

کیسا رہے گا؟

وقت کی پیچیدگی کا تجزیہ تین جوہر کے لئے

  • اوlyل ، ہم ایک بار پہلے عنصر کو ڈھونڈ سکتے ہیں جس کو ہم ٹھیک کرسکتے ہیں۔
  • اندرونی لوپ
  • پہلا عنصر لیتا ہے۔
  • آخر سے دوسرا عنصر لیتا ہے۔
  • خراب صورتحال میں ، ہم شاید پہلے عنصر سے آخری عنصر کی طرف جانا شروع کردیں۔
  • جو O (n ^ 2) کے وقت کی پیچیدگی کا باعث بنتا ہے۔

خلائی پیچیدگی کا تجزیہ تین سم کے لئے

  • ہم ٹریک رکھنے کے لئے صرف کچھ متغیرات کا استعمال کرتے ہیں۔
  • اس طرح ، خلائی پیچیدگی کو O (1) تک لے جانا

ایک چھوٹا سا موافقت

اگر ہم تھری سم دشواری کے اسٹوریج یونٹ کو تبدیل کریں تو کیا ہوگا۔ حیرت زدہ!؟

کچھ خاص نہیں. ہم صرف ایک سے تین مختلف صفوں کو لیں گے۔ صورت میں آپ کو یہ نہیں ملا۔ مجھے نمونہ ٹیسٹ کیس پیش کرنے دو۔

ان پٹ

سرنی 1 = {1 ، 2 ، 3 ، 4 ، 5}

سرنی 2 = {2 ، 3 ، 6 ، 1 ، 2}

سرنی 3 = {3 ، 2 ، 4 ، 5 ، -6}

آؤٹ پٹ

YES

یہاں ایک تصویر ہے جس میں ممکنہ سہولتوں کو اجاگر کیا گیا ہے

تین جمع

مسئلہ تک کیسے پہنچیں

  • اوlyل ، ہم کسی بھی دو صفوں سے رقم کے تمام ممکنہ امتزاج پیدا کرنے کی کوشش کرتے ہیں۔
  • اس کو حاصل کرنے کے ل we ہم دو لوپ چلاتے ہیں
  • تکرار سے بچنے کے ل these ہم ان تمام امتزاج کو ایک سیٹ میں اسٹور کرتے ہیں
  • ہم جائزہ لیتے ہیں کہ کیا مجموعی قیمت کی قیمت تیسری صف میں موجود ہے یا نہیں
  • اگر ہاں تو ہم ہاں میں لوٹتے ہیں
  • آخر میں تمام صفوں کو لوپ کرنے کے بعد بھی اگر ہم 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));
    } 
}

C ++ کوڈ کے لئے تین کا حساب

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی = O (n ^ 2)

کیسا رہے گا؟

  • ہم دوسرے صف سے عنصر تلاش کرنے کے لئے بیرونی لوپ چلاتے ہیں۔
  • اندرونی لوپ میں ، ہم ایک عنصر کو تیسرے صف سے دوسرے صفی عنصر میں شامل کرتے ہیں۔
  • اب تک کی گئی وقت کی پیچیدگی O (n ^ 2) ہے۔
  • اگلی لوپ عنصر کو پہلے صف سے چیک کرتا ہے
  • اس لوپ کے لئے وقت کی پیچیدگی = O (1)
  • ابھی تک حتمی پیچیدگی = O (n ^ 2) + O (1) = O (n ^ 2)

خلائی پیچیدگی = O (n)

کیسا رہے گا؟

  • ہم تمام عناصر کو ذخیرہ کرنے کے لئے ایک سیٹ استعمال کرتے ہیں
  • اس سے O (n) کے وقت کی پیچیدگی پیدا ہوتی ہے