Verilən cəm ilə subarray

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon American Express alma Bloomberg ByteDance Kupanq eBay Facebook Goldman Sachs google LinkedIn microsoft Kahin istədi Twilio Über Arzu Yahoo Yandex
Geyim Sükut HashingBaxılıb 1127

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Verilən cəmi problemi ilə alt bölmədə bir array n müsbət element ehtiva edir. Alt dizinin bütün elementlərinin cəminin bir_suma bərabər olduğu subarrayı tapmalıyıq. Subarray bəzi elementləri massivin başlanğıcından və ya sonundan silərək orijinal massivdən əldə edilir.

misal

a. Giriş massivi: [1, 3, 7, 9, 11, 15, 8, 6]

Cəmi = 19
Çıxış: 1 və 3 → [3, 7, 9], subarray cəmi = 19 olacaqdır

b. Giriş massivi: [1, 3, 7, 9, 11, 15, 8, 6]

Cəmi = 20
Çıxış: 0 və 3 → [1, 3, 7, 9], subray cəmi = 20 olacaqdır

c. Giriş massivi: [1, 3, 7, 9, 11, 15, 8, 6]

Cəmi = 40
Çıxış olacaq: Verilən cəm ilə subarray tapılmadı.

d. Giriş massivi: [4, 3, 2, 8, 9, 11]

Cəmi = 8
Çıxış: 3 və 3 → [8], subarray cəmi = 8 olacaqdır

Yanaşma 1

Alqoritm

Bütün subarraysları nəzərdən keçirin və hər alt dizinin cəmini yoxlayın.

  1. İki döngə işlədin.
  2. Xarici döngə başlanğıc indeksini göstərir.
  3. Daxili döngü bütün subrayları tapır və cəmi tapır.
  4. Cəmi = cari_sum, cari_sum bu subarray, çap başlanğıcı və bitmə indekslərinin cəmidir.

Həyata keçirilməsi

Verilən Cəm ilə Subarray üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int array[], int N, int sum)
{
    int current_sum, i, j;
    //i is start point and j - 1 is end point
    for (i = 0; i < N; i++)
    {
        current_sum = array[i];
        for (j = i+1; j < N + 1; j++)
        {
            if (current_sum == sum)
            {
                cout<<"Subarray with given sum is between indexes "<<i<<" and "<<j-1<<endl; 
                return 1;
            }
            else if (current_sum > sum)
            {
                break;
            }
           current_sum = current_sum + array[j];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarraySum(a,n,sum);
    return 0;
}

Verilən Cəm ilə Subarray üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int N, int sum)
    {
        int current_sum, i, j;
        //i is start point and j - 1 is end point
        for (i = 0; i < N; i++)
        {
            current_sum = array[i];
            for (j = i+1; j < N + 1; j++)
            {
                if (current_sum == sum)
                {
                    System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1)); 
                    return 1;
                }
                else if (current_sum > sum)
                {
                    break;
                }
               current_sum = current_sum + array[j];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
8
1 3 8 9 11 13 17 21
28
Subarray with given sum is between indexes 2 and 4

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (n * n) burada n verilən massivin ölçüsüdür. Burada subarrayın başlanğıc nöqtəsini (i) düzəldirik və j ilə bitən bütün mümkün alt dizinin cəmini hesablayırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Yanaşma 2

Alqoritm

Subarray cəmi yaradın funksiyası massivi və cəmi arqument kimi qəbul edən və verilən cəm ilə alt sətrin başlanğıc və bitmə indekslərini verən.

  1. Əvvəlcə serialın ilk elementi olaraq current_sum başlayın və başlanğıc indeksini 0 olaraq saxlayın.
  2. Current_sum cəmi aşarsa, staring elementini çıxarın və start indeksini artırın.
  3. Current_sum cəmə bərabərdirsə, başlanğıc və bitiş indekslərini qaytarır.
  4. Current_sum-a elementləri bir-bir əlavə edin.
  5. Döngü bitərsə, “given_sum ilə subarray tapılmadı.” Yazdırın.

Verilən cəm ilə subarray üçün tətbiqetmə

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int SubarrySum(int array[], int n, int sum)
{
    //Initialize current_sum = first element.Therefore, start_index =0
    int current_sum = array[0];
    int start_index = 0;
    
    //if current_sum > sum remove last element
    for(int i = 1; i <= n; i++)
    {
        while(current_sum > sum && start_index < i-1)
        {
            current_sum = current_sum - array[start_index];
            start_index++;
        }
        if(current_sum == sum)
        {
            cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
            return 1;
        }
        //Add current element to current_sum
        if(i < n)
        {
          current_sum = current_sum + array[i];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarrySum(a,n,sum);
    return 0;
}

Java Proqramı

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int n, int sum)
    {
            //Initialize current_sum = first element.Therefore, start_index =0
        int current_sum = array[0];
        int start_index = 0;

        //if current_sum > sum remove last element
        for(int i = 1; i <= n; i++)
        {
            while(current_sum > sum && start_index < i-1)
            {
                current_sum = current_sum - array[start_index];
                start_index++;
            }
            if(current_sum == sum)
            {
                System.out.println("Subarray with given sum is between indexes " + start_index + " and " + (i-1)); 
                return 1;
            }
            //Add current element to current_sum
            if(i < n)
            {
              current_sum = current_sum + array[i];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
6
10 6 8 4 3 8
34
No subarray found with given sum

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (n * n) burada n verilən massivin ölçüsüdür. Burada serialı bir dəfə keçirik və şərtləri yoxlayırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »