दोन सम लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले सफरचंद बाइट डान्स अंतर्ज्ञानाने जाणणे मायक्रोसॉफ्ट ओरॅकल
बायनरी शोध दोन पॉइंटर

या समस्येमध्ये, आम्हाला ए मध्ये दोन भिन्न निर्देशांकांची जोडी शोधावी लागेल क्रमवारी लावली अॅरे की त्यांची मूल्ये दिलेल्या लक्ष्यात भर घालतात. अ‍ॅरे फक्त आहे असे आपण समजू शकतो एक पूर्ण संख्येची जोड जोडीची बेरीज करते. एरे मध्ये वर्गीकरण केल्याचे लक्षात घ्या कमी होत नाही रीतीने

उदाहरण

Array = {1 , 2 , 3 , 4 , 5}
Target = 6
1 5
Array = {1 , 4 , 5 , 11 , 12}
Target = 9
2 3

अ‍ॅप्रोच (ब्रूट फोर्स)

हा दृष्टीकोन सरळ आहे. आम्ही अ‍ॅरेमधील प्रत्येक जोडी शोधू शकतो आणि जर त्यांची बेरीज दिलेल्या लक्ष्याइतकी असेल तर त्यांचे निर्देशांक मुद्रित करा. या प्रकारची ब्रुट फोर्स सोल्यूशनमध्ये अ‍ॅरे मधील प्रत्येक संभाव्य जोड्या आणि संभाव्य जोड्यांची संख्या तपासणे आवश्यक आहे एन * (एन - 1) / 2. तर, सर्वात वाईट परिस्थितीत, हा दृष्टीकोन धीमा होऊ शकतो.

अल्गोरिदम

  1. अ‍ॅरेमध्ये सोल्यूशनची पहिली अनुक्रमणिका राखण्यासाठी लूप चालवा
  2. प्रत्येक प्रथम पूर्णांकासाठी समाधानाची दुसरी अनुक्रमणिका राखण्यासाठी आणखी एक पळवाट चालवा
  3. कोणत्याही क्षणी, दोन निर्देशांकांच्या मूल्यांची बेरीज लक्ष्याइतकीच असेल
    • त्याचे निर्देशांक मुद्रित करा

टू सम लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int n = a.size();
    for(int i = 0 ; i < n - 1 ; i++)
        for(int j = i + 1 ; j < n ; j++)
        {
            if(a[i] + a[j] == target)
                return {i + 1 , j + 1};
        }
    return {};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

जावा कार्यक्रम

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        for(int i = 0 ; i < a.length - 1 ; i++)
            for(int j = i + 1 ; j < a.length ; j++)
            {
                if(a[i] + a[j] == target)
                    return new int[]{i + 1 , j + 1};
            }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}
2 3

टू सम लेटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एन), जेथे अ‍ॅरेचा एन = आकार. आम्ही शक्य जोडी तपासत आहोत आणि जोड्यांची एकूण संख्या आहेः एन * (एन - 1) / 2.

जागेची जटिलता

ओ (1). केवळ चल करीता स्थिर जागा वापरली जाते.

दृष्टीकोन (दोन पॉइंटर)

अल्गोरिदम

द्या अ‍ॅरे आहे क्रमवारी लावली. हे एक विशेष प्रकरण आहे कारण आम्हाला माहिती आहे की जर आपण प्रथम निर्देशांक निश्चित केला असेल तर लक्ष्य पूर्ण करण्यासाठी आवश्यक मूल्य अ‍ॅरेमध्ये पुढे सापडेल. बायनरी शोध. 

एक समान दृष्टीकोन वापरला जाऊ शकतो: आम्ही वापरू शकतो दोन पॉइंटर्स: डावे आणि बरोबर, मुळात प्रथम आणि ते शेवटचा अनुक्रमे अ‍ॅरेचा घटक. त्यानंतर आम्ही या दोन पॉइंटर मूल्यांच्या बेरीजची तुलना लक्ष्यशी करू शकतो. जर मूल्ये आणि लक्ष्यांची बेरीज समान असेल तर आपल्याला ती सापडली फक्त उपाय. तर आम्ही ही अनुक्रमणिका जोडी परत करतो. अन्यथा, जर मूल्यांची बेरीज असेल कमी उद्दीष्टापेक्षा, आम्हाला पॉइंटर्सपैकी एक वाढविणे किंवा त्याचे भाड्याने देणे आवश्यक आहे. अर्थात आम्ही आणत आहोत योग्य केवळ शेवटपासून पॉईंटर. तर, आपण वाढवू या बाकी पॉईंटर आणि त्याच अवस्थेसाठी तपासा. त्याचप्रमाणे जर मूल्यांची बेरीज लक्ष्यापेक्षा जास्त असेल तर आपण ती कमी करू योग्य पॉईंटर

सॉर्ट केलेल्या अ‍ॅरे लीटकोड सोल्युशन्समध्ये लक्ष्य करण्यासाठी दोन पूर्णांक जोडले जातात

ची अंमलबजावणी दोन सम लीटकोड सोल्यूशन

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

vector <int> targetSum(vector <int> &a , int &target)
{
    int left = 0 , right = int(a.size()) - 1 , tempSum;
    while(left < right)
    {
        tempSum = a[left] + a[right];
        if(tempSum == target)
            return {left + 1 , right + 1};
        if(tempSum > target)
            right--;
        else
            left++;
    }
    return {-1 , -1};
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 11 , 12};
    int target = 9;
    for(int &x : targetSum(a , target))
        cout << x << " ";
    cout << '\n';
}

जावा कार्यक्रम

class target_sum
{
    static int[] targetSum(int []a , int target)
    {
        int left = 0 , right = a.length - 1 , tempSum;
        while(left < right)
        {
            tempSum = a[left] + a[right];
            if(tempSum == target)
                return new int[]{left + 1 , right + 1};
            if(tempSum > target)
                right--;
            else
                left++;
        }
        return new int[]{-1 , -1};
    }


    public static void main(String args[])
    {
        int [] a = {1 , 4 , 5 , 11 , 12};
        int target = 9;

        for(int x : targetSum(a , target))
            System.out.print(x + " ");
    }
}
2 3

टू सम लेटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), अगदी सर्वात वाईट परिस्थितीतही, आम्ही अ‍ॅरेमधील सर्व घटकांना एकदाच भेट देतो.

जागेची जटिलता

ओ (1). आम्ही व्हेरिएबल्ससाठी स्थिर जागा वापरतो.