იპოვნეთ ქვეჯგუფი მოცემული თანხით (ამუშავებს ნეგატიურ რიცხვებს)


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon კუპონი დუნია ადგილზე მიტანა GE Healthcare ინფოეჯი Moonfrog ლაბორატორიები
Array Hash მოცურების ფანჯარა

პრობლემა "იპოვნეთ ქვეჯგუფი მოცემული თანხით (სახელურები უარყოფით რიცხვებზე)" აცხადებს, რომ თქვენ გეძლევათ მთელი რიცხვი მასივი, შეიცავს უარყოფით მთელ რიცხვებსაც და რიცხვს, სახელწოდებით "ჯამი". პრობლემის დებულება ითხოვს ქვე-მასივის დაბეჭდვას, რომელიც აჯამებს მოცემულ რიცხვს, სახელწოდებით "sum". თუ ჩვენს გამოსვლაში ერთზე მეტი ქვე-მასივია, დაბეჭდეთ რომელიმე მათგანი.

მაგალითი

იპოვნეთ ქვეჯგუფი მოცემული თანხით (ამუშავებს ნეგატიურ რიცხვებს)

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

ალგორითმი

  1. გამოაცხადეთ ა რუკა.
  2. უცნობია მიმდინარე ჯამი to 0.
  3. მასივის გადაკვეთა, ხოლო მე <n,
    1. აჯამებს currentSum და მასივის ელემენტის მნიშვნელობას და შეინახეთ currentSum.
    2. შეამოწმეთ არის თუ არა currentSum ტოლი ჯამის.
      • თუ სიმართლეა, შემდეგ დაბეჭდე ინდექსი 0-ით i- ზე და გატეხე.
    3. შეამოწმეთ, შეიცავს თუ არა რუქა მიმდინარე მნიშვნელობას.
      • თუ სიმართლეა, ამობეჭდეთ ინდექსები, როგორც რუკის currentSum მნიშვნელობა i- ზე და break.
    4. თუ რომელიმე მოცემული პირობა არ აკმაყოფილებს, ეს ნიშნავს, რომ მოცემულ ჯამში ვერაფერი ვიპოვნეთ.

განმარტება

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

განვიხილოთ მაგალითი:

მაგალითი

arr [] = {14, 1, -10, 20, 1}, ჯამი = 5

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

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, ახლა ჩვენს ამჟამინდელ ჯამში გვაქვს 14, შეამოწმებთ არის თუ არა ტოლი მოცემული ჯამი, რომელიც არის 5, და ეს მცდარია, შემდეგ შეამოწმებთ, შეიცავს თუ არა რუკა მიმდინარე თანხა, რომელიც ნიშნავს 14-5 = 9 ასევე არასწორია. ასე რომ, ჩვენ გავივლით შემდეგ ელემენტს. ასე რომ, ჩვენ დაამატეთ მიმდინარეSum და i რუკაში.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, ახლა ჩვენს მიმდინარე ჯამში გვაქვს 15, ჩვენ შეამოწმებთ არის თუ არა ტოლი მოცემული ჯამის, მაგრამ ის არ აკმაყოფილებს, ჩვენ გავაგრძელებთ თუ რუკა შეიცავს ამჟამინდელ ჯამს, რომელიც არის 15-5-10, ასევე არასწორია. ასე რომ, ჩვენ დაამატეთ მიმდინარეSum და i რუკაში.

i = 2, მიმდინარე ჯამი = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, ახლა ჩვენს მიმდინარე ჯამში გვაქვს 15, გადავამოწმებთ არის თუ არა ტოლი მოცემული ჯამი, რომელიც არის 5 და აღმოვაჩინეთ, რომ მდგომარეობა კმაყოფილია, ნიშნავს რომ მივიღეთ ჩვენი გამომავალი, შემდეგ ჩვენ დავბეჭდავთ ქვეჯგუფის ინდექსებს i- მდე.

კოდი

C ++ კოდი მოცემული ჯამით ქვეჯგუფის მოსაძებნად (ამუშავებს უარყოფით რიცხვებს)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

ჯავის კოდი მოცემული ჯამით ქვეჯგუფის მოსაძებნად (ამუშავებს უარყოფით რიცხვებს)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

სირთულის ანალიზი

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

O (N) სადაც "N" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (N) სადაც "N" არის მასივის ელემენტების რაოდენობა.