ሁለት ድምር ሌትኮድ መፍትሔ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ፓም ByteDance ኢላማዊ የ Microsoft በ Oracle
ስልተ የሁለትዮሽ ፍለጋ ምስጠራ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions ሁለት ጠቋሚ

በዚህ ችግር ውስጥ ሀ ውስጥ ሁለት የተለያዩ ማውጫዎችን ጥንድ ማግኘት አለብን መደርደር ደርድር የእነሱ እሴቶች ከተሰጠ ዒላማ ጋር እንደሚደመሩ። ድርድሩ ብቻ እንዳለው መገመት እንችላለን አንድ የታለመውን ድምር የሚጨምሩ ጥንድ ቁጥሮች። ድርድሩ በ ውስጥ የተስተካከለ መሆኑን ልብ ይበሉ የማይቀንስ መልክ.

ለምሳሌ  

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 * N) ፣ የት ድርድር N = መጠን። ሊሆኑ የሚችሉትን ጥንድ ስንመረምር እና የአጠቃላይ ጥንዶች ቁጥር- N * (N - 1) / 2.

ተመልከት
የ Excel ሉህ አምድ ቁጥር Leetcode መፍትሔ

የቦታ ውስብስብነት

ኦ (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

የሁለት ሱም ሌትኮድ መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ በጣም በከፋ ሁኔታ ውስጥ እንኳን ፣ ሁሉንም በአንድ ላይ ብቻ በድርድሩ ውስጥ ያሉትን ንጥረ ነገሮች እንጎበኛለን ፡፡

ተመልከት
ሁለት ሕብረቁምፊዎችን ለመስራት አነስተኛ ደረጃዎች የእርምጃዎች Leetcode መፍትሔዎች

የቦታ ውስብስብነት

ኦ (1). ለተለዋዋጮች ቋሚ ቦታ እንጠቀማለን ፡፡