ორი ჯამი Leetcode ამოხსნა  


Რთული ტური Easy
ხშირად ეკითხებიან Apple ByteDance Intuit microsoft Oracle
ალგორითმები ორობითი ძებნა კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode 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. თუ რომელიმე წერტილში, ორი ინდექსის მნიშვნელობების ჯამი მიზნის ტოლია
    • დაბეჭდეთ მისი ინდექსები

განხორციელება ორი Sum 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';
}

ჯავა პროგრამა

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 ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (N * N), სადაც N = მასივის ზომა. როგორც ჩვენ ვამოწმებთ შესაძლო წყვილს, და წყვილების საერთო რაოდენობაა: N * (N - 1) / 2.

იხილეთ ასევე
Excel ფურცლის სვეტის ნომერი Leetcode გადაწყვეტა

კოსმოსური სირთულის

O (1). ცვლადების მხოლოდ მუდმივი სივრცეა გამოყენებული.

მიდგომა (ორი მაჩვენებელი)  

ალგორითმი

მისცეს მასივი არის დალაგებულია. ეს განსაკუთრებული შემთხვევაა, რადგან ჩვენ ვიცით, რომ თუ ჩვენ დავაფიქსირეთ პირველი ინდექსი, მას შემდეგ, რაც მიზნის მისაღწევად საჭიროა საჭირო მნიშვნელობა, ორობითი ძებნა. 

მსგავსი მიდგომის გამოყენება შეიძლება: ჩვენ შეგვიძლია გამოვიყენოთ ორი მაჩვენებელი: მარცხნივ და უფლება, შინაგანად პირველი და ბოლო მასივის ელემენტი შესაბამისად. ამის შემდეგ შეგვიძლია შევადაროთ ამ ორი მაჩვენებლის მნიშვნელობების ჯამი მიზანს. თუ მნიშვნელობებისა და სამიზნეების ჯამი ტოლია, ჩვენ აღმოვაჩინეთ მხოლოდ გამოსავალი ამრიგად, ჩვენ ვაბრუნებთ ამ ინდექსურ წყვილს. წინააღმდეგ შემთხვევაში, თუ ღირებულებების ჯამია ნაკლები ვიდრე სამიზნე, ჩვენ უნდა გავზარდოთ ან დავამციროთ ერთ-ერთი მაჩვენებელი. ცხადია, ჩვენ შემოგვყავს უფლება მაჩვენებელი მხოლოდ ბოლოდან. ასე რომ, ჩვენ უნდა გავზარდოთ დარჩა მაჩვენებელი და შეამოწმეთ იგივე მდგომარეობა. ანალოგიურად, თუ მნიშვნელობების ჯამი მიზანზე მეტია, ჩვენ ვამცირებთ უფლება მაჩვენებელი

ორი მთელი რიცხვი უმატებენ სამიზნეს დალაგებულ მასივში 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';
}

ჯავა პროგრამა

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 ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (N), როგორც უარეს შემთხვევაშიც, მასივის ყველა ელემენტს მხოლოდ ერთხელ ვსტუმრობთ.

იხილეთ ასევე
ნაბიჯების მინიმალური რაოდენობა ორი სტრიქონის შესაქმნელად Anagram Leetcode Solutions

კოსმოსური სირთულის

O (1). ცვლადებისათვის ვიყენებთ მუდმივ ადგილს.