चार तत्वहरू फेला पार्नुहोस् जुन दिइएको मान (हशम्याप) मा जोडिन्छ


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन गुगल माइक्रोसफ्ट
एरे हैश क्रमबद्ध

समस्या "दिईएको मान (ह्यासम्याप) मा जोडिएको चार तत्वहरू फेला पार्नुहोस्" भन्छ कि मानौं, तपाईसँग पूर्णांक एरे र योग भनिन्छ। समस्या कथन निर्धारित गर्न सोध्छ यदि एरेमा चार तत्वहरू उपस्थित छन् जुन दिईएको मान "योग" को योगफल हुन्छ। यदि सहि छ भने, तब कार्यहरू आउटपुट गर्दछ "हो", अन्यले "होईन"।

उदाहरणका

चार तत्वहरू फेला पार्नुहोस् जुन दिइएको मान (हशम्याप) मा जोडिन्छ

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. लूप पार गर्नुहोस्, जबकि म <एन - १.
    1. लूप पार गर्नुहोस्, जबकि j = i + 1 <n
      1. एरको मूल्य भण्डार गर्नुहोस् [i] + एर [जे] भल गर्न र जाँच गर्नुहोस् कि ह्यास तालिकामा योगफल-भोल छ।
        1. यदि सहि छ भने, तब कुञ्जी प्राप्त गर्नुहोस् र नम्बर फेला पार्नुहोस्, र सत्यमा फर्कनुहोस्।
      2. अर्को, त्यो हरू टेबलमा I र j राख्नुहोस् कुञ्जीसँग अरको रूपमा [i] + एर [j]।
  2. गलत फर्काउनुहोस्।

स्पष्टीकरण

हामीलाई एक समस्या कथन दिइन्छ जुन निर्धारित गर्न सोध्छ यदि त्यहाँ एरेमा चार एलिमेन्टहरू छन् जुन दिईएको मूल्यको योगफल दिन्छ। यदि हो भने, पछ्याउनुहोस् त्यसपछि फंक्शनले हो प्रिन्ट गर्नुपर्दछ, अन्य मुद्रण गर्नुहोस्। हामी प्रयोग गर्न जाँदैछौं हसिhing यो समस्या समाधान गर्न। त्यस कारणले गर्दा हामी कुञ्जीलाई हाम्रो एलिमेन्टको रूपमा भण्डार गर्न सक्दछौं जुन सम्भावित सब-एरे हुन जोड्दछ, र हाम्रो अनुक्रमणिकाको रूपमा यसको मान गर्दछौं ताकि हामी यसलाई जाँच गर्न सक्दछौं।

हामी एक उदाहरण विचार गरौं:

उदाहरणका

एआर [] = {२,,,,, २,,,,,,,} sum, योग = २ 2

यहाँ हामीले उदाहरण लिएका छौं। हामीले घोषणा गरेका छौं बूलियन फंक्शन जुन सत्य र गलत फिर्ता गर्न गइरहेको छ। हामी मानचित्रमा कुन वस्तु प्रयोग गर्न लागेका छौं, हाम्रो नक्सामा प्रयोग गर्न गइरहेका छौं हाम्रो तर्क मध्ये कुनै सूची वा भेक्टर हो। त्यसोभए मूलत: हामी एर्रेहरू पार गर्न जाँदैछौं, तर एर्रेको प्रत्येक एलिमेन्ट एक पटकमा बाहिरी लूपमा लिन्छौं र अर्को एन्ट्रु लूपको साथ अगाडि बढ्ने एलिमेन्टहरू, जुन एक इन्डेक्स अगाडि आउँछ।

हामी दुबै दुबै तत्वको जोड लिन्छौं जुन एर [i] + एर [j] छ र यसलाई केही भ्यारीएबल भनिन्छ भ्यालोमा भण्डार गर्छौं र जाँच गर्छौं यदि जोड-भेल उपस्थित छ भने ह्याशटेबल वा होईन यदि छैन भने मात्र एलिमेन्ट्सलाई नक्शामा धकेल्नुहोस्, मानौं हामीसँग एर्रेको एलिमेन्ट २ र (छ (एर [i] र एर [j]) योगफल is हो र २--2 को १ 7-योगफल २ ह्यास तालिकामा उपस्थित छैन, त्यसैले हामी simple र हालको अनुक्रमणिका ० र १ लाई धक्का दिन्छौं, ताकि पछि हामी पत्ता लगाउन सक्दछौं कि तालिकामा सम-एर [i] + एर [j] छ कि छैन वा छैन। यदि अवस्थित छ भने, त्यसपछि केवल कुञ्जीको मानहरू लिनुहोस् र यसमा केही सर्तहरू जाँच्नुहोस्, यदि यो सन्तुष्ट भयो भने सत्य फिर्ता हुनेछ। यसको मतलब हामीले हाम्रो उत्तर भेट्टायौं।

C ++ कोड चार तत्वहरू फेला पार्नको लागि जुन दिइएको मूल्य (ह्यासम्याप) मा जोडिन्छ

#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

जटिलता विश्लेषण

समय जटिलता

O (n2जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। ह्यासम्याप प्रयोग गर्नाले हामीलाई यो समय जटिलता प्राप्त गर्न अनुमति दिएको अन्यथा यो सम्भव थिएन।

ठाउँ जटिलता

O (n2जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। सबैभन्दा नराम्रो अवस्थामा त्यहाँ N ^ २ जोडी हुन सक्छ जुन नक्शामा भण्डारण गर्न आवश्यक पर्दछ। यसैले अन्तरिक्ष जटिलता बहुपद हो।