Субрайро бо суммаи додашуда ёбед (Ададҳои манфиро идора мекунад)  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon КупонДуния Деҳлӣ GE Тандурустӣ InfoEdge Озмоишгоҳҳои Moonfrog
тартиботи ҳарбӣ Хаш Равзанаи Sliding

Масъалаи "Ҷудокуниро бо суммаи додашуда ёбед (Ададҳои манфиро идора мекунад)" мегӯяд, ки ба шумо ан ҳамаҷониба асал, дорои ададҳои манфӣ ва рақаме бо номи "сум". Дар изҳороти масъала чоп кардани зеркатрасма, ки то шумораи додашуда бо номи "сум" ҷамъ оварда мешавад, дархост карда мешавад. Агар зиёда аз як sub-массив ҳамчун баромади мо мавҷуд бошад, ягонтои онҳоро чоп кунед.

мисол  

Субрайро бо суммаи додашуда ёбед (Ададҳои манфиро идора мекунад)пайвандак

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. Эълом кунед a харита.
  2. маҷмӯи ҳозир ба 0.
  3. Массивро тай кунед, дар ҳоле ки i <n,
    1. Арзиши currentSum ва унсури массивро ҷамъбаст намуда, ба currentSum нигоҳ доред.
    2. Санҷед, ки оё ҳаҷми ҳозира ба маблағ баробар аст.
      • Агар рост бошад, пас индексро аз 0 то i чоп кунед ва шикастед.
    3. Тафтиш кунед, ки харита дорои арзиши ҷории Sumum-sum аст.
      • Агар рост бошад, пас индексҳоро ҳамчун арзиши ҷории ҳосили харита ба i чоп кунед ва шикаст диҳед.
    4. Агар ягон шарти додашуда қонеъ нашавад, ин маънои онро дорад, ки мо бо маблағи додашуда чизе наёфтем.

Шарҳ

Ба мо як изҳороти проблемавӣ дода мешавад, ки дархост мекунад, ки зерматрибро, ки то ҳосили додашударо ҷамъ мекунад, муайян намоем ва агар зиёда аз як sub-массиви ёфтшуда бошад, пас ягонтои онро чоп кунед. Мо истифода бурданием HashMap ва мо ба нигоҳ доштани арзиши ҳозир ва индекси он, агар ҳеҷ яке аз шартҳо пас аз илова кардани ҳар як унсури асал ва currentSum (ки ҳамчун 0 пештар оғоз карда шуда буд).

ҳамчунин нигаред
Subarray калонтарин бо шумораи баробари 0s ва 1s

Биёед як мисолро дида бароем:

мисол

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

Мо як массиви бутуни додаем, ки он дорои якчанд ададҳои манфӣ ва ҷамъи адад мебошад. Мо бояд суб-массивро ёбем, ки ба шумораи додашуда, сум илова мешавад. Ҳангоми сайр аз тамоми массив мо бояд currentSum-и худро нигоҳ дорем, ин ба мо имкон медиҳад, ки зеркатри имконпазирро ба даст орем.

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, ҳоло мо дар currentSum 14 дорем, мо ба суммаи додашудаи 5 баробар буданро тафтиш мекунем ва ин дурӯғ аст, пас мо тафтиш мекунем, ки харита дорои currentSum-sum, ки маънои 14-5 = 9 -ро дорад, низ нодуруст аст. Ҳамин тавр, мо аз унсури навбатӣ мегузарем. Ҳамин тавр, мо currentSum ва i-ро ба харита илова мекунем.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, ҳоло мо дар currentSum 15 дорем, мо месанҷем, ки он ба маблағи додашуда баробар аст, аммо қонеъ намешавад, мо барои он хоҳем рафт, ки агар харита дорои currentSum-sum мебошад, ки 15-5-10 низ нодуруст аст. Ҳамин тавр, мо currentSum ва i-ро ба харита илова мекунем.

i = 2, ҷорииСум = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, акнун мо дар currentSum 15 дорем, мо ба суммаи додашудаи 5 баробар буданашро тафтиш мекунем ва фаҳмидем, ки шарт қаноатманд аст, ин маънои онро дорад, ки мо натиҷаи худро ба даст овардем, пас мо индекси subarray 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

Таҳлили мураккабӣ  

Мураккабии вақт

О (Н) ки дар "N" шумораи унсурҳои массив аст.

ҳамчунин нигаред
Воридшавӣ

Мураккабии фазо

О (Н) ки дар "N" шумораи унсурҳои массив аст.