সমস্ত যোগফল 0 টি যোগ করে মুদ্রণ করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ফ্রিচার্জ প্রকৃতপক্ষে তথ্য প্রান্ত মাইক্রোসফট ওয় রুমগুলি
বিন্যাস কাটা

আপনাকে একটি পূর্ণসংখ্যা অ্যারে দেওয়া হবে, আপনার টাস্কটি সমুদ্রের সমষ্টি সহ সমস্ত সম্ভাব্য সাব-অ্যারে মুদ্রণ করা we সুতরাং আমাদের 0 সাবমের সাথে সমস্ত সাববারে মুদ্রণ করা দরকার।

উদাহরণ

সমস্ত যোগফল 0 টি যোগ করে মুদ্রণ করুন

arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

অ্যালগরিদম

  1. কিছু ভ্যারিয়েবলের সাথে অ্যারের উপাদানগুলির যোগফলটি যোগফলটি 0 সহ উপ-অ্যারের একটি ট্র্যাক রাখতে "যোগ" বলুন say
  2. If সমষ্টি 0 হিসাবে পাওয়া যায় এটির অর্থ সম্ভাব্য সাব-অ্যারে 0 থেকে বর্তমান সূচীতে পাওয়া যায়।
  3. চেক করুন যদি সমষ্টি উপরের প্রক্রিয়া থেকে এটি পাওয়া যায়, আমাদের উপস্থিত মানচিত্র অথবা না.
  4. যদি মানচিত্রে যোগফল থাকে তবে এর অর্থ এটি পূর্ববর্তী সাব-অ্যারের মোট যোগফল এবং বর্তমান সূচকগুলি অবধি এটি উপাদানটির যোগফল হয়ে যায়।
  5. মানচিত্রটিতে বর্তমান যোগফলটি উপস্থিত না থাকলে sertোকান।

ব্যাখ্যা

আমরা ব্যবহার করতে যাচ্ছি হ্যাশ কারণ, এটির সাহায্যে আমরা সাব-অ্যারে এবং তাদের সূচকগুলিতে নজর রাখতে পারি। এছাড়াও, আমরা বিভিন্ন সংগ্রহ ব্যবহার করতে যাচ্ছি। প্রথমে আমাদের অ্যারেতে সমস্ত সংখ্যা খুঁজে বের করতে হবে যা সমষ্টি 0 সহ সম্ভাব্য সাব-অ্যারে গঠন করে that এর জন্য, আমরা অ্যারের উপাদানগুলি যুক্ত করব এবং এটি যোগফলের জন্য সঞ্চয় করব। সমষ্টিটি ইতিমধ্যে শুরুতে শুরু করা হয়েছিল।

আমরা একটি মানচিত্র তৈরি করব যা কী হিসাবে অস্থায়ী যোগফল এবং মান হিসাবে একটি ভেক্টর থাকবে। সুতরাং, এখানে ভেক্টর সূচকগুলি উপস্থাপন করে যেখানে ইনপুট শুরু থেকে উপাদানগুলির যোগফল বর্তমান যোগফলের সমান।

এটির পরে, আমরা অ্যারে পেরিয়ে শুরু করি start সুতরাং, আমরা এগিয়ে চলার সাথে সাথে উপাদানগুলিকে একটি চলক যোগে যুক্ত করতে থাকি। যদি সমষ্টি যে কোনও মুহুর্তে 0 হতে দেখা গেছে। সুতরাং, এর অর্থ এই যে শুরু থেকে সাব-অ্যারেটি 0 হয় এবং এছাড়াও যদি এমন কিছু সূচক পাওয়া যায় যা সমষ্টি 0 এর সমান হয়।

যদি যোগফল শূন্য হয় না পাওয়া যায়। তারপরে আমরা পরীক্ষা করে দেখি যে মানচিত্রে সেই যোগফল রয়েছে। মানচিত্রে গণনাফল না থাকলে। তারপরে বর্তমান সূচীতে শেষ হওয়া এবং যোগফলের যোগফল নেই এমন কোন সাববারে বিদ্যমান নেই সুতরাং, সমস্ত উপ-অ্যারেগুলি সন্ধান করার পরে যা বর্তমান সূচীতে শেষ হয় এবং সমান 0 এর সমান হয়। আমরা বর্তমান সূচকে ভেক্টরে যোগ করব কী হিসাবে বর্তমান যোগফল রয়েছে এমন মানচিত্র।

তবে মানচিত্রে যোগফল থাকলে এর অর্থ আমরা কিছু পূর্ববর্তী সাব-অ্যারে পেয়েছি যার সমষ্টি ছিল। তারপরে আমাদের সেই যোগফল এবং সূচকগুলির মান যুক্ত করতে হবে।

এবং এর বাইরে, আমরা আমাদের তালিকাটি ফিরিয়ে আনলাম যা আমরা ভেক্টর হিসাবে ঘোষণা করেছি। সেখান থেকে যদি ফেরতের মানটির আকার 0 থাকে তবে এর অর্থ আমরা খুঁজে পাই নি যে আর কোনও আউটপুট মুদ্রিত হবে না।

সি ++ কোড 0 টি সমষ্টি সহ সমস্ত সাবহারিকে মুদ্রণ করতে

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
  unordered_map<int, vector<int> > Map;
  vector <pair<int, int>> result;
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    sum += arr[i];
    if (sum == 0)
      result.push_back(make_pair(0, i));
        if (Map.find(sum) != Map.end())
    {
      vector<int> vec = Map[sum];
      for (auto val = vec.begin(); val != vec.end(); val++)
        result.push_back(make_pair(*val + 1, i));
    }
    Map[sum].push_back(i);
  }
  return result;
}
void print(vector<pair<int, int>> result)
{
  for (auto j= result.begin(); j != result.end(); j++)
    cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
    int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
  vector<pair<int, int> > result = getSubArray(arr, n);
  if (result.size() == 0)
    cout << "No such Sub-array exists";
  else
    print(result);

  return 0;
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

জাভা কোড সমস্ত subarrays মুদ্রণ 0 যোগ সঙ্গে

import java.util.*;
class Pair
{
    int start, end;
    Pair(int a, int b)
    {
        start = a;
        end = b;
    }
}
class printSubArray0Sum
{
    public static ArrayList<Pair> getSubArray(int[] arr, int n)
    {
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Pair> temp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
                temp.add(new Pair(0, i));
            ArrayList<Integer> list = new ArrayList<>();
            if (map.containsKey(sum))
            {
                list = map.get(sum);
                for (int j = 0; j < list.size(); j++)
                {
                    temp.add(new Pair(list.get(j) + 1, i));
                }
            }
            list.add(i);
            map.put(sum, list);
        }
        return temp;
    }
    public static void print(ArrayList<Pair> result)
    {
        for (int i = 0; i < result.size(); i++)
        {
            Pair pair = result.get(i);
            System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
        }
    }
    public static void main(String args[])
    {
        int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
        int n = arr.length;

        ArrayList<Pair> result = getSubArray(arr, n);
        if (result.size() == 0)
            System.out.println("No such Sub-array exists");
        else
            print(result);
    }
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।