Өгөгдсөн нийлбэр бүхий дэд массивыг олох (Сөрөг тоотой харьцах)


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны КупонДуниа Дели GE Эрүүл мэндийн InfoEdge Moonfrog лабораторууд
Array Хаш Гулгадаг цонх

"Өгөгдсөн нийлбэр бүхий дэд мөрийг олох (Сөрөг тоонуудыг зохицуулах)" гэсэн бодлогод танд ан өгөгдсөн болно бүхэл тоо массив, сөрөг бүхэл тоонууд ба "нийлбэр" гэсэн тоог агуулна. Асуудлын шийдэл нь "нийлбэр" гэсэн өгөгдсөн тоог нэгтгэсэн дэд массивыг хэвлэхийг хүсдэг. Хэрэв бидний гаралтын хувьд нэгээс олон дэд массив байгаа бол тэдгээрийн аль нэгийг нь хэвлээрэй.

Жишээ нь

Өгөгдсөн нийлбэр бүхий дэд массивыг олох (Сөрөг тоотой харьцах)

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. Массивыг дайрч, харин би <n,
    1. CurrentSum ба массив элементийн утгыг нэгтгэж currentSum-д хадгална.
    2. CurrentSum нь нийлбэртэй тэнцүү эсэхийг шалгана уу.
      • Хэрэв үнэн бол индексийг 0 болгож i гэж хэвлээд завсарлана.
    3. Газрын зураг нь currentSum-sum гэсэн утгатай эсэхийг шалгана уу.
      • Хэрэв үнэн бол индексүүдийг газрын зургийн одоогийн Sum-ийн утга болгож i болгож, завсарлана.
    4. Хэрэв өгөгдсөн нөхцлүүдийн аль нэг нь хангаагүй бол бид тухайн нийлбэртэй юу ч олоогүй гэсэн үг юм.

Тайлбар

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

Нэг жишээг авч үзье.

Жишээ нь

arr [] = {14, 1, -10, 20, 1}, нийлбэр = 5

Бид бүхэл тоон массивыг өгсөн бөгөөд үүнд зарим сөрөг бүхэл тоонууд болон тооны нийлбэр багтсан болно. Бид өгөгдсөн тоог нэмсэн дэд массивыг олох ёстой. Бүх массивыг дайран өнгөрөхдөө бид одоогийн Sum-ийг хадгалах ёстой бөгөөд энэ нь боломжит дэд массивыг өгөх болно.

i = 0, currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14, одоо бидний одоо байгаа Sum-д 14 байгаа бөгөөд энэ нь өгөгдсөн 5-тай тэнцэж байгаа бөгөөд энэ нь худал бол газрын зураг нь дараах агуулгатай эсэхийг шалгана. 14-5 = 9 гэсэн утгатай нийлбэр нь бас худал байна. Тиймээс бид дараагийн элементийг дамжин өнгөрөх болно. Тиймээс бид currentSum ба i-г газрын зураг дээр нэмнэ.

i = 1, currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15, currentSum = 15, одоо манай SumSum-д 15 байна, өгөгдсөн нийлбэртэй тэнцүү байгаа эсэхийг шалгана, гэхдээ ханахгүй байна, бид газрын зураг нь currentSum-sum гэсэн утгыг агуулдаг бөгөөд 15-5-10 нь мөн худлаа болно. Тиймээс бид currentSum ба i-г газрын зураг дээр нэмнэ.

i = 2, одоогийн нийлбэр = 15,

currentSum = currentSum + arr [i] => 15 + (-10), currentSum = 5, одоо манай SumSum-д 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" массив дахь элементүүдийн тоо юм.