Երկու գումարած Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են խնձոր ByteDance Intuit Microsoft Պատգամախոս
Երկուական որոնում Երկու ցուցիչ

Այս խնդրում մենք պետք է գտնենք զույգ երկու հստակ ցուցանիշներ ա-ում տեսակավորված է դասավորություն որ դրանց արժեքները գումարվում են տվյալ թիրախին: Կարող ենք ենթադրել, որ զանգվածն ունի միայն մեկ ամբողջ թվերի զույգ, որոնք ավելանում են նպատակային գումարին: Նշենք, որ զանգվածը տեսակավորված է ա չնվազող ձեւով:

Օրինակ

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. Runանգվածի լուծույթի առաջին ցուցիչը պահպանելու համար գործարկեք օղակ
  2. Գործարկեք մեկ այլ օղակ `յուրաքանչյուր առաջին ամբողջ թվերի համար լուծման երկրորդ ինդեքսը պահպանելու համար
  3. Եթե ​​որևէ կետում, երկու ցուցանիշների արժեքների հանրագումարը հավասար է նպատակայինին
    • Տպեք դրա ցուցանիշները

Իրականացում երկու գումարի Leetcode լուծման

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

Java ծրագիր

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

Երկու գումարի Leetcode լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

O (N * N), որտեղ N = զանգվածի չափը: Երբ մենք ստուգում ենք հնարավոր զույգի առկայությունը, և զույգերի ընդհանուր քանակն է. N * (N - 1) / 2:

Տիեզերական բարդություն

Ո (1), Փոփոխականների համար օգտագործվում է միայն հաստատուն տարածք:

Մոտեցում (երկու ցուցիչ)

Ալգորիթմ

Տվեք զանգվածը տեսակավորված: Սա հատուկ դեպք է, քանի որ մենք գիտենք, որ եթե մենք առաջին ինդեքսն ենք ֆիքսել, ապա թիրախը կատարելու համար անհրաժեշտ արժեքը զանգվածում կգտնվի առջևում երկուական որոնում: 

Նման մոտեցում կարող է օգտագործվել. Մենք կարող ենք օգտագործել երկու ցուցիչ ՝ ձախ և ճիշտ, intally է առաջին եւ անցյալ համապատասխանաբար զանգվածի տարրը: Դրանից հետո մենք կարող ենք համեմատել այս երկու ցուցիչի արժեքների գումարը թիրախի հետ: Եթե ​​արժեքների և թիրախի հանրագումարը հավասար են, ապա մենք գտել ենք այն միայն լուծում Այսպիսով, մենք վերադարձնում ենք այս ինդեքսային զույգը: Հակառակ դեպքում, եթե արժեքների գումարն է ավելի քիչ քան թիրախը, մենք պետք է ավելացնենք կամ որոշենք ցուցիչներից մեկը: Ակնհայտ է, որ մենք բերում ենք այն իրավունք ցուցիչ միայն վերջից: Այսպիսով, մենք պետք է ավելացնենք դուրս ցուցիչ և ստուգել նույն պայմանը: Նմանապես, եթե արժեքների հանրագումարը նպատակայինից ավելին է, մենք նվազեցնում ենք իրավունք ցուցիչ

Երկու ամբողջական թվեր, որոնք հավաքվում են նպատակային Leetcode Solutions զանգվածում

Իրականացում Երկու գումարած 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';
}

Java ծրագիր

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 լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ նույնիսկ ամենավատ դեպքում, մենք այցելում ենք զանգվածի բոլոր տարրերը միայն մեկ անգամ:

Տիեզերական բարդություն

Ո (1), Մենք օգտագործում ենք անընդհատ տարածություն փոփոխականների համար: