Берилген сумма менен субарраны табыңыз (Терс сандар менен иштейт)  


Кыйынчылык деңгээли орто
Көп суралган Amazon CouponDunia Delhivery GE Саламаттыкты сактоо InfoEdge Moonfrog Labs
согуштук тизме таштанды Жылма терезе

"Берилген суммасы бар субарраны тап (Терс сандар менен иштейт)" маселеси сизге an берилгенин билдирет бүтүн согуштук тизме, терс бүтүн сандарды жана "сумма" деп аталган санды камтыйт. Маселе коюлуп, берилген суммадагы "сумма" деп аталган суб-массивди басып чыгарууну суранат. Эгерде биздин чыгарылышыбыз катары бир нече суб-массив катышса, алардын бирин басып чыгарыңыз.

мисал  

Берилген сумма менен субарраны табыңыз (Терс сандар менен иштейт)төөнөч

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.

Algorithm  

  1. Декларация a карта.
  2. коюлган currentSum 0 үчүн.
  3. Массивди кыдырып, ал эми i <n,
    1. CurrentSum жана массив элементинин маанисин суммалап, currentSum чейин сактайт.
    2. CurrentSum суммасына барабар экендигин текшериңиз.
      • Эгер чын болсо, анда индексти 0 деп i деп чыгарып, бузуп коюңуз.
    3. Картада currentSum-sum мааниси бар экендигин текшериңиз.
      • Эгер чын болсо, анда индекстерди картанын учурдагы суммасы катары басып чыгарыңыз i жана break.
    4. Эгерде берилген шарттардын бири дагы канааттандырбаса, анда берилген сумма менен эч нерсе тапкан жокпуз.

түшүндүрүү

Бизге берилген суммага чейинки суб-массивди аныктоону сураган көйгөйдү чечмелеп беришкен жана эгерде бир нече суб-массив табылса, анда алардын бирин басып чыгар. Биз колдоно турган болдук HashMap жана биз наркты сактайбыз currentSum жана анын индекси, эгерде ар бир элементин кошкондон кийин шарттардын бири дагы канааттандырылбаса согуштук тизме жана currentSum (ал 0 мурун башталган).

ошондой эле
0s жана 1s бирдей сандагы ири subarray

Келгиле, бир мисал карап көрөлү:

мисал

arr [] = {14, 1, -10, 20, 1}, сумма = 5

Бир катар терс сандарды камтыган бүтүндөй массивди жана сандык сумманы бердик. Берилген санга, суммага кошулган кичи массивди табышыбыз керек. Жалпы массивди аралап өтүп, учурдагы сумманы сактап турушубуз керек, бул бизге мүмкүн болгон суб-массивди берет.

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, эми биздин CurrentSumдо 14 бар, ал берилген суммага барабар экендигин 5ке, ал эми жалган болсо, анда картада 14-5 = 9 дегенди билдирген учурдагы сумма дагы жалган. Ошентип, биз кийинки элемент аркылуу өтөт. Ошентип, currentSum жана i карталарына кошобуз.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, азыр биздин CurrentSumдо 15 бар, анын берилген суммага барабар экендигин текшеребиз, бирок ал канааттанбайт, эгерде биз барабыз картада 15-5-10 суммасындагы учурдагы сумма дагы жалган. Ошентип, currentSum жана i карталарына кошобуз.

i = 2, учурдагы сумма = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, эми биздин CurrentSumдо 15 бар, анын берилген суммага барабар экендигин 5ке текшерип, шартты таптык канааттандырылат, биз өзүбүздүн өндүрүмүбүздү алдык дегенди билдирет, андан кийин 0 кичирейтмесинин индексин 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

Берилген сумма менен субарраны табуу үчүн Java коду (Терс сандарды иштетет)

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" массивдеги элементтердин саны.