கொடுக்கப்பட்ட வரிசைக்கான அனைத்து தனிப்பட்ட துணை-வரிசைத் தொகையின் தொகையைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் கிரே ஆரஞ்சு intuit மைக்ரோசாப்ட் நாகரோ
அணி ஹாஷ் வரிசையாக்க

உங்களிடம் முழு எண் உள்ளது என்று வைத்துக்கொள்வோம். “கொடுக்கப்பட்ட வரிசைக்கான அனைத்து தனித்துவமான துணை-வரிசைத் தொகையின் கூட்டுத்தொகையைக் கண்டுபிடி” என்ற சிக்கல் அனைத்து தனித்துவமான துணை வரிசைகளின் கூட்டுத்தொகையைக் கண்டுபிடிக்கக் கேட்கிறது (துணை வரிசைத் தொகை என்பது ஒவ்வொரு துணை வரிசையின் உறுப்புகளின் கூட்டுத்தொகை).

தனித்துவமான துணை-வரிசை தொகை மூலம், எந்த துணை வரிசைக்கு ஒரே மதிப்பு இல்லை என்று சொல்ல வேண்டும்.

உதாரணமாக

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

கொடுக்கப்பட்ட வரிசைக்கான அனைத்து தனிப்பட்ட துணை-வரிசைத் தொகையின் தொகையைக் கண்டறியவும்

அல்காரிதம்

  1. ஒரு அறிவிக்கவும் வரைபடம்.
  2. தொகுப்பு வெளியீடு க்கு 0.
  3. வரிசையை i = 0 முதல் i வரை பயணிக்கவும்
    1. அமைக்க தொகை 0 வரை.
    2. வரிசையை j = i, j க்கு பயணிக்கவும்
      • தொகைக்கு arr [j] இன் மதிப்பைச் சேர்க்கவும்.
      • தொகை மற்றும் அதன் நிகழ்வை வரைபடத்தில் சேர்க்கவும்.
  4. வரைபடத்தில் பயணித்து, அந்த விசையின் உள்ளீடுகளின் மதிப்பு 1 என சரிபார்க்கவும்.
    1. நிபந்தனை திருப்தி அடைந்த போதெல்லாம் வெளியீட்டின் விசைகளின் மதிப்பைச் சேர்க்கவும்.
  5. வெளியீடு திரும்பவும்.

விளக்கம்

எங்களுக்கு ஒரு வழங்கப்படுகிறது முழு வரிசை. அனைத்து தனிப்பட்ட துணை வரிசைகளின் கூட்டுத்தொகையைக் கண்டுபிடிப்பதே எங்கள் பணி. ஒவ்வொரு துணை வரிசையின் கூட்டுத்தொகையும் ஒவ்வொரு துணை வரிசையின் தனிமத்தின் கூட்டுத்தொகையாக இருக்கும். நாங்கள் பயன்படுத்தப் போகிறோம் ஹாஷிங் இந்த கேள்வியை தீர்க்க. I இன் மதிப்பை மாற்றும்போதெல்லாம் ஒரு வரிசையின் ஒவ்வொரு உறுப்புகளையும் எடுத்து, தொகையை 0 ஆகத் தொடங்குவோம். நாம் உள் வளையத்திற்குள் நுழையும்போது, ​​ஒரு வரிசையிலிருந்து பயணிப்போம் i க்கு n, மற்றும் வரிசை மற்றும் தொகையின் ஒவ்வொரு மதிப்பையும் சேர்க்கிறது. பின்னர் ஒரே நேரத்தில் தொகையையும் அதன் நிகழ்வையும் வரைபடத்தில் சேமிக்கிறோம். முழு வரிசையையும் பார்வையிட்ட பிறகு, சாத்தியமான அனைத்து துணை வரிசைகளையும் கண்டுபிடிக்கவும். அதன்பிறகு, வரைபடத்தில் அந்த தொகைகளை ஒரு முறை மட்டுமே தேடுகிறோம். தனித்துவமான துணை வரிசைகளின் தொகையை நாம் விரும்புவதால், தனித்துவமான தொகைகளைக் கொண்ட பொருள். ஆகவே, வரைபடத்தில் ஒரு முறை நிகழும் தொகையை நாம் கண்டறிந்தால், அதன் அதிர்வெண் 1 என்று சொல்லும் போது, ​​அந்தத் தொகைகளின் மதிப்பை வெளியீட்டில் சேர்த்து புதுப்பிப்போம்.

அதற்கான உதாரணத்தைக் கருத்தில் கொண்டு:

உதாரணமாக

arr [] = {3, 1, 4, 5}

முதலில், நாம் i = 0 ஐ வைத்திருக்கிறோம், பின்னர் 3 ஐ ஒரு உறுப்பாகக் கொண்டுள்ளோம், நாங்கள் 3 இலிருந்து தொடங்குவோம், 3 இல் தொகையைச் சேர்த்து 3 ஐ வரைபடத்தில் புதுப்பிப்போம், பின்னர் 1 ஐ கூட்டுத்தொகையாகச் சேர்த்து, 4 ஐ வரைபடத்தில் புதுப்பிப்போம் , பின்னர் 4 ஐ ஒரு தனிமமாக எடுத்து, 7 ஐ வரைபடத்தில் சேர்க்கிறது. இந்த வழியில், 5 ஐப் பார்வையிட்டு 12 வரைபடத்தை புதுப்பித்த பிறகு முதல் பயணத்தை முடிப்போம்.

ஆகவே, 4 ஐ ஒரு உறுப்பாக எடுத்து 4 இலிருந்து தொடங்கும் போது, ​​தொகையை வரைபடத்தில் புதுப்பிப்போம், ஏனெனில், 4 ஏற்கனவே உள்ளது வரைபடம், அதன் அதிர்வெண்ணை அதிகரிப்போம், மேலும் அதிர்வெண் 1 இல்லாத தொகைகளை நாங்கள் புறக்கணிப்போம். இந்த வழியில், தனித்துவமான துணை வரிசைகளை நாம் கையாள முடியும்.

குறியீடு

கொடுக்கப்பட்ட வரிசைக்கான அனைத்து தனிப்பட்ட துணை-வரிசைத் தொகைகளையும் கண்டுபிடிக்க சி ++ குறியீடு

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

கொடுக்கப்பட்ட வரிசைக்கான அனைத்து தனிப்பட்ட துணை-வரிசைத் தொகைகளையும் கண்டுபிடிக்க ஜாவா குறியீடு

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்2எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஏனென்றால் நாங்கள் 2 உள்ளமை சுழல்களைப் பயன்படுத்தியுள்ளோம், தொகையைத் தேடுவது O (1) இல் ஹாஷ்மேப்பைப் பயன்படுத்தி செய்யப்படுகிறது.

விண்வெளி சிக்கலானது

O (n ^ 2) எங்கே “N” என்பது வரிசையின் உறுப்புகளின் எண்ணிக்கை. ஏனெனில் மிக மோசமான நிலையில் நாம் n ^ 2 வெவ்வேறு துணை வரிசை தொகைகளைக் கொண்டிருக்கலாம்.