څلور عناصر ومومئ چې ورکړل شوي ارزښت سره برابر وي (هاشمپ)


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د ګوګل د Microsoft
پیشه هاش ترتیب کول

ستونزه "څلور عناصر ومومئ چې ورکړل شوي ارزښت سره تړاو لري (هاشامپ)" وایی چې فرض کړئ ، تاسو د انډییر سرنی لرئ او د شمیرو په نامه شمیره. د ستونزې بیان غوښتنه کوي ترڅو مشخص کړي که چیرې څلور عناصر په صف کې شتون ولري کوم چې ورکړل شوي ارزښت "مجموعه" پورې اړه لري. که ریښتیا وي ، نو بیا "هو" ترسره کړئ ، او بل "نه".

بېلګه

څلور عناصر ومومئ چې ورکړل شوي ارزښت سره برابر وي (هاشمپ)

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. د آرر ارزښت وټاکئ [i] + آرر [j] ویل ته او چیک کړئ چې د مخلوط ویل په هش جدول کې شتون لري.
        1. که ریښتیا وي ، نو بیا کیلي ترلاسه کړئ او شمیره یې ومومئ ، او ریښتیني راستون شئ.
      2. بل ، دا i او j د هش په میز کې د کیر سره د آرر په توګه وساتئ [i] + ارر [j].
  2. غلط راستنیدل.

تشریح

موږ ته د یوې ستونزې بیان ورکړل شوی چې پوښتنه یې ترې کوي چې ایا دلته څلور عناصر شتون لري چې په صف کې شتون لري چې ورکړل شوي ارزښت یې پوره کوي. که هو ، بیا یې تعقیب کړئ نو فنکشن باید هو چاپ کړي ، نور یې چاپ کړئ. موږ کارولو ته ځو ټوپونه د دې ستونزې د حل لپاره. د دې له امله ، موږ کولی شو کلیدي زموږ د عنصر په توګه زیرمه کړو کوم چې ممکنه فرعي سرې جوړه وي ، او زموږ د دې شاخصونو ارزښت ته ارزښت ورکوو ترڅو موږ وکولی شو پدې کې چیک شو.

راځئ چې یوه بېلګه په نظر کې ونیسو:

بېلګه

تیر [] = {2 ، 7 ، 3 ، 2 ، 9 ، 5 ، 9 ، 3} ، جمع = 25

دلته موږ یو مثال اخیستی. موږ اعالن کړی بولین هغه فعالیت چې سم او باطل ته به ورسیږي. موږ د اعتراض ملکیت هم کاروو چې د کومو شیانو چې موږ یې کاروو ، زموږ نقشه کې ، لکه څنګه چې زموږ یو دلیل کوم لیست یا ویکتور دی. نو اساسا موږ د سریز څخه تیریږو ، مګر په یو وخت کې د سري هر عنصر په بیروني لوپ کې اخیستل او پاتې نور عناصر چې یو لړلیک مخ ته راځي ، د دوهم داخلي لوپ سره.

موږ د دواړه عناصرو مجموعه اخلو چې تیر دی [i] + آرر [j] او دا د ویل په نامه ځینې متغیر ته زیرمه کوو او بیا یې ګورو چې جم-ویل په کې شتون لري که نه هشتبل یا نه ، که موجود نه وي نو په ساده ډول په نقشه کې عناصر وباسئ ، فرض کړئ چې موږ د صف د عنصر 2 او 7 لرو (آرر [i] او تیر [j]] ترلاسه کول 9 او د جمعیت ارزښت چې 25-9 دی 18 دی د هیش په میز کې شتون نلري ، نو موږ 9 او اوسني شاخصونه ساده فشار ورکوو چې 0 او 1 دي ، نو وروسته به موږ وموندل شي چې سم ارر [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 (n)2هلته "n" په صف کې د عناصرو شمیر دی. د هاش میپ کارول موږ ته اجازه راکړئ د دې وخت پیچلتیا لاسته راوړو که نه نو دا به ممکن نه وي.

د ځای پیچلتیا

O (n)2هلته "n" په صف کې د عناصرو شمیر دی. په بدترین حالت کې ممکن د N ^ 2 جوړې شتون ولري چې په نقشه کې زیرمه کولو ته اړتیا لري. په دې توګه د ځای پیچلتیا ډیره ده.