پیدا کردن زیر مجموعه با جمع داده شده (دسته های منفی)  


سطح دشواری متوسط
اغلب در آمازون کوپن دونیا تحویل کالا GE بهداشت و درمان InfoEdge آزمایشگاه Moonfrog
صف مخلوط پنجره کشویی

مسئله "پیدا کردن زیر مجموعه با جمع داده شده (دسته های منفی اعداد)" بیان می کند که به شما داده می شود عدد صحیح صف، حاوی عددهای صحیح منفی و همچنین یک عدد به نام "sum" است. بیانیه مسئله می خواهد آرایه فرعی را چاپ کند ، که در مجموع یک عدد مشخص به نام "sum" است. اگر بیش از یک زیر آرایه به عنوان خروجی ما وجود دارد ، هر یک از آنها را چاپ کنید.

مثال  

پیدا کردن زیر مجموعه با جمع داده شده (دسته های منفی)سنجاق

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. اعلام الف نقشه.
  2. تنظیم فعلی به 0.
  3. آرایه را رد کنید ، در حالی که من <n,
    1. مقدار جریان و مقدار عنصر آرایه را جمع می کند و آن را در جریان فعلی ذخیره می کند.
    2. بررسی کنید که آیا جریانSum برابر با جمع است.
      • اگر درست است ، سپس شاخص را به صورت 0 در i چاپ کرده و شکست دهید.
    3. بررسی کنید که آیا نقشه حاوی مقدار currentSum-sum است.
      • اگر درست است ، شاخص ها را به عنوان مقدار currentSum نقشه در i چاپ کنید و break کنید.
    4. اگر هر یک از شرایط داده شده راضی نباشد ، به این معنی است که با مبلغ داده شده چیزی پیدا نکردیم.

توضیح

به ما یک عبارت مساله داده شده است که می خواهد زیر آرایه جمع شده در مجموع را پیدا کند و اگر بیش از یک زیر آرایه وجود دارد ، هر یک از آنها را چاپ کنید. ما قصد استفاده از HashMap و ما می خواهیم مقدار فعلی و شاخص آن در صورتی که بعد از جمع کردن هر عنصر از هیچ یک از شرایط برآورده نشود صف و currentSum (که قبلاً 0 شروع شد).

همچنین مشاهده کنید
بزرگترین زیر مجموعه با تعداد برابر 0 و 1

اجازه بدین مثالی را مطرح کنیم:

مثال

arr [] = {14 ، 1 ، -10 ، 20 ، 1} ، مجموع = 5

ما یک آرایه عدد صحیح داده ایم که حاوی چند عدد صحیح منفی است و همچنین یک عدد جمع دارد. ما باید زیر آرایه زیر را جمع کنیم که به عدد داده شده ، جمع می شود. در حالی که کل آرایه را رد می کنیم ، باید جریان فعلی خود را حفظ کنیم ، این همان آرایه فرعی است.

i = 0 ، currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14 ، اکنون 14 در currentSum خود داریم ، بررسی خواهیم کرد که آیا برابر با مجموع داده شده 5 است یا نه ، و این نادرست است ، سپس بررسی خواهیم کرد که آیا نقشه حاوی sum-sum به معنی 14-5 = 9 نیز نادرست است. بنابراین عنصر بعدی را مرور خواهیم کرد. بنابراین currentSum و i را به نقشه اضافه می کنیم.

i = 1 ، currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15 ، currentSum = 15 ، در حال حاضر ما 15 در currentSum خود داریم ، بررسی خواهیم کرد که آیا برابر با مقدار داده شده است اما راضی نیست ، ما به دنبال اگر نقشه حاوی sumSum است که 15-5-10 است نیز نادرست است. بنابراین currentSum و i را به نقشه اضافه می کنیم.

i = 2 ، currentSum = 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

کد جاوا برای یافتن زیرآرایه با جمع داده شده (دسته های منفی شماره)

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" تعداد عناصر آرایه است.