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


कठिनाई स्तर आसान
में अक्सर पूछा सेब ByteDance सहज माइक्रोसॉफ्ट ओरेकल
एल्गोरिदम द्विआधारी खोज कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस दो सूचक

इस समस्या में, हमें एक में दो अलग-अलग सूचकांकों की एक जोड़ी ढूंढनी होगी छाँटे गए सरणी उनके मान किसी दिए गए लक्ष्य तक जुड़ते हैं। हम मान सकते हैं कि सरणी में ही है एक पूर्णांकों की जोड़ी जो लक्ष्य राशि तक जोड़ते हैं। ध्यान दें कि सरणी एक में सॉर्ट की गई है गैर घटते तौर तरीका।

उदाहरण  

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

दृष्टिकोण (जानवर बल)  

यह दृष्टिकोण सीधा है। हम सरणी में प्रत्येक जोड़ी की जांच कर सकते हैं और यदि उनका योग दिए गए लक्ष्य के बराबर है, तो उनके सूचकांकों को प्रिंट करें। इस प्रकार का जानवर सेना समाधान के लिए हर संभावित जोड़ी और सरणी में संभावित जोड़े की संख्या की जांच करना आवश्यक है = n * (n - 1) / 2 तो, सबसे खराब स्थिति में, यह दृष्टिकोण धीमा हो सकता है।

कलन विधि

  1. सरणी में समाधान के पहले सूचकांक को बनाए रखने के लिए एक लूप चलाएँ
  2. हर पहले पूर्णांक के लिए समाधान का दूसरा सूचकांक बनाए रखने के लिए एक और लूप चलाएं
  3. यदि किसी भी बिंदु पर, दो सूचकांकों के मूल्यों का योग लक्ष्य के बराबर है
    • इसके सूचकांकों को प्रिंट करें

दो सम लेटेकोड सॉल्यूशन का कार्यान्वयन

C ++ प्रोग्राम

#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

दो सम लेटेकोड सॉल्यूशन की जटिलता विश्लेषण

समय जटिलता

ओ (एन * एन), जहाँ N = सरणी का आकार। जैसा कि हम संभावित जोड़ी की जांच करते हैं, और जोड़े की कुल संख्या हैं: एन * (एन - 1) / 2।

यह भी देखें
एक्सेल शीट कॉलम नंबर लेटकोड सॉल्यूशन

अंतरिक्ष की जटिलता

ओ (1)। चर के लिए केवल निरंतर स्थान का उपयोग किया जाता है।

दृष्टिकोण (दो सूचक)  

कलन विधि

देना सरणी है हल किया हुआ। यह एक विशेष मामला है क्योंकि हम जानते हैं कि यदि हमने पहला इंडेक्स तय कर लिया है तो लक्ष्य को पूरा करने के लिए आवश्यक मान ऐरे उपयोग में आगे पाया जा सकता है। द्विआधारी खोज। 

एक समान दृष्टिकोण का उपयोग किया जा सकता है: हम उपयोग कर सकते हैं दो संकेत: बाएँ और सही, अंत में प्रथम और पिछली बार क्रमशः सरणी का तत्व। फिर हम इन दो पॉइंटर मानों के योग की तुलना लक्ष्य से कर सकते हैं। यदि मान और लक्ष्य का योग बराबर है, तो हमने पाया है केवल समाधान। इसलिए, हम इस सूचकांक जोड़ी को वापस करते हैं। अन्यथा, यदि मानों का योग है कम लक्ष्य की तुलना में, हमें एक संकेत को बढ़ाने या बदलने की आवश्यकता है। जाहिर है, हम ला रहे हैं सही केवल अंत से सूचक। इसलिए, हमें वेतन वृद्धि करनी चाहिए बाएं सूचक और उसी स्थिति के लिए जाँच करें। इसी तरह, यदि मानों का योग लक्ष्य से अधिक है, तो हम योग को घटाते हैं सही सूचक।

दो पूर्णांकों को एक क्रमबद्ध सरणी Leetcode Solutions में लक्ष्य तक जोड़ना है

का कार्यान्वयन दो सम लेटेकोड सॉल्यूशन

C ++ प्रोग्राम

#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)। हम चर के लिए निरंतर स्थान का उपयोग करते हैं।