கொடுக்கப்பட்ட மதிப்பைக் குறிக்கும் நான்கு கூறுகளைக் கண்டறியவும் (ஹாஷ்மேப்)


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

“கொடுக்கப்பட்ட மதிப்புக்கு (ஹாஷ்மேப்) கூட்டுத்தொகையான நான்கு கூறுகளைக் கண்டுபிடி” என்ற சிக்கல் கூறுகிறது, உங்களிடம் ஒரு முழு வரிசை மற்றும் தொகை எனப்படும் எண் உள்ளது. கொடுக்கப்பட்ட மதிப்பு “கூட்டுத்தொகை” எனக் கூறப்படும் வரிசையில் நான்கு கூறுகள் உள்ளதா என்பதைத் தீர்மானிக்க சிக்கல் அறிக்கை கேட்கிறது. உண்மை என்றால், செயல்பாடு வெளியீடுகள் “ஆம்”, இல்லையெனில் “இல்லை”.

உதாரணமாக

கொடுக்கப்பட்ட மதிப்பைக் குறிக்கும் நான்கு கூறுகளைக் கண்டறியவும் (ஹாஷ்மேப்)

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

அல்காரிதம்

  1. சுழற்சியைக் கடந்து, நான் <n - 1 போது.
    1. சுழற்சியைக் கடந்து, j = i + 1 <n
      1. Ar [i] + arr [j] இன் மதிப்பை val க்கு சேமித்து, ஹாஷ் அட்டவணையில் sum-val இருக்கிறதா என்று சோதிக்கவும்.
        1. உண்மை என்றால், விசையைப் பெற்று எண்ணைக் கண்டுபிடித்து, உண்மைக்குத் திரும்புக.
      2. இல்லையெனில், அந்த i மற்றும் j ஐ ஹாஷ் அட்டவணையில் விசையுடன் சேர்த்து arr [i] + arr [j] என வைக்கவும்.
  2. பொய் திரும்பவும்.

விளக்கம்

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

ஒரு உதாரணத்தைக் கருத்தில் கொள்வோம்:

உதாரணமாக

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, தொகை = 25

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

Ar [i] + arr [j] எனப்படும் இரண்டு உறுப்புகளின் கூட்டுத்தொகையை எடுத்து அதை வால் எனப்படும் சில மாறியில் சேமித்து, பின்னர் கூட்டுத்தொகை வால் உள்ளதா என சரிபார்க்கவும் ஹேஷ்டேபிள் அல்லது இல்லையென்றால், உறுப்புகளை வரைபடத்தில் தள்ளுங்கள், நம்மிடம் வரிசையின் உறுப்பு 2 மற்றும் 7 (அர் [i] மற்றும் அர் [ஜே]) பெறப்படும் தொகை 9 என்றும், கூட்டு மதிப்பு 25-9 என்று 18 என்றும் கூறலாம் ஹாஷ் அட்டவணையில் இல்லை, எனவே 9 மற்றும் தற்போதைய குறியீடுகளை 0 மற்றும் 1 என்று எளிமையாக தள்ளுவோம், இதன் மூலம் கூட்டுத்தொகை [i] + arr [j] அட்டவணையில் இருக்கிறதா இல்லையா என்பதை பின்னர் கண்டுபிடிக்கலாம். இருந்தால், விசையின் மதிப்புகளைப் பெற்று, அதில் சில நிபந்தனைகளைச் சரிபார்க்கவும், அது திருப்தி அடைந்தால் உண்மைக்குத் திரும்புக. இதன் பொருள் எங்கள் பதிலைக் கண்டுபிடித்தோம்.

கொடுக்கப்பட்ட மதிப்புக்கு (ஹாஷ்மேப்) நான்கு கூறுகளைக் கண்டறிய சி ++ குறியீடு

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

கொடுக்கப்பட்ட மதிப்புக்கு (ஹாஷ்மேப்) நான்கு கூறுகளைக் கண்டறிய ஜாவா குறியீடு

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

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

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

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

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

ஓ (என்2எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. மோசமான நிலையில், வரைபடத்தில் சேமிக்க வேண்டிய N ^ 2 ஜோடிகள் இருக்கலாம். இதனால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.