د دوه Sum Leetcode حل  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي مڼه ByteDance Intuit د Microsoft سينه_پوښ
الگوريتم دوه لمبري پلټنه کوډ ورکول مرکه د مرکې چمتووالی لیټ کوډ د لیټ کوډ حلونه دوه نښې

پدې ستونزه کې ، موږ باید په a کې د دوه جلا شاخصونو یوه جوړه ومومئ ترتیب شوی سور چې د دوی ارزښتونه ورکړل شوي هدف ته اضافه کوي. موږ کولی شو فرض کړو چې صف یوازې لري یو د انډیجر جوړه چې د موخې مجموعې ته اضافه کوي. په یاد ولرئ چې صف په a کې ترتیب شوی دی نه کمیدونکی لاره.

بېلګه  

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. که په هر وخت کې ، د دوه شاخصونو د ارزښتونو مجموعه د هدف سره مساوي وي
    • خپل شاخصونه چاپ کړئ

د دوه Sum لیټکوډ حل پلي کول

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

د دوه Sum لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N * N) ، چیرې چې N = د صف اندازه. لکه څنګه چې موږ د احتمالي جوړه لپاره ګورو ، او د جوړه جوړه جوړه په لاندې ډول ده: N * (N - 1) / 2.

هم وګوره
د ایکسل شیټ کالم نمبر لیټکوډ حل

د ځای پیچلتیا

O (1). د تغیراتو لپاره یوازې ثابت ځای کارول کیږي.

چلند (دوه نښې)  

الګوریتم

د ورکولو صف دی ترتیب شوی. دا یوه ځانګړې قضیه ده ځکه چې موږ پوهیږو چې که موږ لومړی شاخص ټاکلی وي نو د هدف پوره کولو لپاره اړین ارزښت په کارولو سره په صف کې مخکې وموندل شي دوه لمبري پلټنه. 

ورته ورته چلند کارول کیدی شي: موږ وکاروو دوه نښې: کی left او سم، په اصل کې لومړی او د وروستی په ترتیب سره د صفونو عنصر. بیا موږ کولی شو د دې دوه نښې ارزښتونو مجموعې هدف ته پرتله کړو. که د ارزښتونو او هدف مجموعه مساوي وي ، نو بیا یې موندلې یوازې حل. نو ، موږ دا شاخص جوړه کړه. نور ، که د ارزښتونو مجموعه وي لږ د هدف په پرتله ، موږ اړتیا لرو یو له نښو څخه زیاتوالی یا پریکړې ترمیم. په ښکاره ډول ، موږ دا راوړو حق يواځې د پای نه. نو ، موږ باید د پاتې اشاره او ورته حالت لپاره وګورئ. په ورته ډول ، که د ارزښتونو ارزښت له هدف څخه ډیر وي ، موږ کمو حق نغوت

په ترتیب شوي صف کې د لیټکوډ حلونو کې د هدف لپاره دوه بشپړونکي اضافه کولقید

د د دوه Sum Leetcode حل

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

د دوه Sum لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N) ، لکه څنګه چې حتی په بدترین حالت کې ، موږ یوازې په صف کې ټول عناصر لیدو.

هم وګوره
د دوه سټریز انګګرام لیټکوډ حلونو جوړولو لپاره د ګامونو لږترلږه شمیره

د ځای پیچلتیا

O (1). موږ د متغیرو لپاره ثابت ځای کاروو.