ပေးထားသော Sum နှင့်အတူ Subarray


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ American Express Apple ဘလွန်းဘာ့ဂ် ByteDance ကွမ်းခြံကုန်း ကို eBay Facebook က Goldman Sachs Google LinkedIn တို့ Microsoft က Oracle က Quera Twilio Uber ဆုတောင်း Yahoo က Yandex
အခင်းအကျင်း hash တားဆီးခြင်း

ပြProbleနာဖော်ပြချက်

ပေးထားသောပေါင်းလဒ်ပြproblemနာနှင့်အတူ subarray အတွက်ကျနော်တို့တစ်ခုပေးပြီ အခင်းအကျင်း positive အပြုသဘောဒြပ်စင်င်။ subarray ၏အစိတ်အပိုင်းအားလုံး၏စုစုပေါင်းသည်ဒေတာတစ်ခုနှင့်တူသည်။ Subarray သည်မူရင်းခင်းကျင်းခြင်းမှရရှိသောအချို့သောအရာများအားလုံးကိုအစသို့မဟုတ်အဆုံးမှဖယ်ရှားခြင်းဖြစ်သည်။

နမူနာ

က။ Input ခင်းကျင်းသည် [၁၊ ၃၊ ၇၊ ၉၊ ၁၁၊ ၁၅၊ ၈၊ ၆]

ပေါင်းလဒ် = 19
Output ဖြစ်လိမ့်မည်: 1 နှင့် 3 → [3, 7, 9], subarray ပေါင်းလဒ် = 19

ခ။ Input ခင်းကျင်းသည် [၁၊ ၃၊ ၇၊ ၉၊ ၁၁၊ ၁၅၊ ၈၊ ၆]

ပေါင်းလဒ် = 20
Output ဖြစ်လိမ့်မည်: 0 နှင့် 3 → [1, 3, 7, 9], subarray ပေါင်းလဒ် = 20

ဂ။ Input ခင်းကျင်းသည် [၁၊ ၃၊ ၇၊ ၉၊ ၁၁၊ ၁၅၊ ၈၊ ၆]

ပေါင်းလဒ် = 40
ပေးထားသောပေါင်းလဒ်နှင့်အတူ subarray မျှရှာပါလိမ့်မည် output ကိုဖြစ်လိမ့်မည်။

။ Input ခင်းကျင်းသည် [၄၊ ၃၊ ၂၊ ၈၊ ၉၊ ၁၁]

ပေါင်းလဒ် = 8
ရလဒ် ၃ ဖြစ်လိမ့်မည်။ ၃ နှင့် ၃ → [3] subarray sum = 3

ချဉ်းကပ်နည်း 1

algorithm

subarrays များအားလုံးကိုသုံးသပ်ပြီး subarray တိုင်း၏ပမာဏကိုစစ်ဆေးပါ။

  1. ကွင်းနှစ်ခုသုံးပါ။
  2. အပြင်ကွင်းဆက်သည်အညွှန်းကိုပြသည်။
  3. အတွင်းပိုင်းကွင်းဆက်သည် subarrays များအားလုံးကိုတွေ့ပြီးပေါင်းလဒ်ကိုတွေ့ရှိသည်။
  4. sum = current_sum ဆိုလျှင် current_sum သည်လက်ရှိ subarray၊ print start နှင့် end index များ၏ပေါင်းလဒ်ဖြစ်သည်။

အကောင်အထည်ဖော်ရေး

ပေးထားသောပမာဏနှင့် Subarray အတွက် C ++ အစီအစဉ်

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

Subarray အတွက် Java အစီအစဉ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n * n) n သည်ပေးထားသောခင်းကျင်း၏အရွယ်အစားဖြစ်သည်။ ဤတွင်ကျွန်ုပ်တို့သည် subarray ၏စမှတ် (i) ကို fix ပြီး j တွင်အဆုံးသတ်နိုင်သောဖြစ်နိုင်သမျှ subarray ၏ပေါင်းလဒ်ကိုတွက်ချက်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ဒီမှာအရန်နေရာမရှိဘူး။

ချဉ်းကပ်နည်း 2

algorithm

subarray ပေါင်းလဒ်တစ်ခုဖန်တီးပါ function ကို ၎င်းသည် array နှင့် sum ကိုအငြင်းအခုံအဖြစ်ယူပြီး subarray ၏အစနှင့်အဆုံးအညွှန်းများကိုပေးသည်။

  1. current_sum ကို array ထဲမှပထမဆုံးဒြပ်စင်အဖြစ်စတင်ပြီး start index ကို 0 အဖြစ်ထားပါ။
  2. current_sum သည် sum ထက်ကျော်လျှင် staring element နှင့် increment start index ကိုဖယ်ရှားပါ။
  3. current_sum သည်ညီမျှပါက start and end indexes ကိုပြန်ပို့သည်။
  4. current_sum တစ်ခုကို element တစ်ခုချင်းစီထည့်ပါ။
  5. အကယ်၍ ကွင်းဆက်ပြီးဆုံးသွားပါက“ given_sum ဖြင့် subarray မျှရှာမတွေ့ပါ” ဟု print ထုတ်ပါ။

ပေးထားသောပမာဏနှင့်အတူ Subarray အတွက်အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#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 အစီအစဉ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n * n) n သည်ပေးထားသောခင်းကျင်း၏အရွယ်အစားဖြစ်သည်။ ဤတွင်ကျွန်ုပ်တို့သည်ခင်းကျင်းမှုကိုတစ်ကြိမ်ဖြတ်ကျော်ပြီးအခြေအနေများကိုစစ်ဆေးသည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ဒီမှာအရန်နေရာမရှိဘူး။

ကိုးကား