ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯಕ್ಕೆ (ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್) ಒಟ್ಟು ನಾಲ್ಕು ಅಂಶಗಳನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಅರೇ ಹ್ಯಾಶ್ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

“ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯಕ್ಕೆ (ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್) ಒಟ್ಟು ನಾಲ್ಕು ಅಂಶಗಳನ್ನು ಹುಡುಕಿ” ಎಂಬ ಸಮಸ್ಯೆ ಹೇಳುತ್ತದೆ, ನೀವು ಒಂದು ಪೂರ್ಣಾಂಕ ರಚನೆ ಮತ್ತು ಮೊತ್ತ ಎಂಬ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದ್ದೀರಿ. ನಿರ್ದಿಷ್ಟ ಹೇಳಿಕೆ “ಮೊತ್ತ” ಕ್ಕೆ ಸೇರುವ ನಾಲ್ಕು ಅಂಶಗಳು ರಚನೆಯಲ್ಲಿ ಇದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಲು ಸಮಸ್ಯೆ ಹೇಳಿಕೆ ಕೇಳುತ್ತದೆ. ನಿಜವಾಗಿದ್ದರೆ, ಫಂಕ್ಷನ್ uts ಟ್‌ಪುಟ್‌ಗಳು “ಹೌದು”, ಇಲ್ಲದಿದ್ದರೆ “ಇಲ್ಲ” ಎಂದು ನೀಡುತ್ತದೆ.

ಉದಾಹರಣೆ

ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯಕ್ಕೆ (ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್) ಒಟ್ಟು ನಾಲ್ಕು ಅಂಶಗಳನ್ನು ಹುಡುಕಿ

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] ನ ಮೌಲ್ಯವನ್ನು ವಾಲ್ ಗೆ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಹ್ಯಾಶ್ ಟೇಬಲ್‌ನಲ್ಲಿ ಮೊತ್ತ-ಮೌಲ್ಯವಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.
        1. ನಿಜವಾಗಿದ್ದರೆ, ಕೀಲಿಯನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ.
      2. ಇಲ್ಲದಿದ್ದರೆ, ಆ ಐ ಮತ್ತು ಜೆ ಅನ್ನು ಹ್ಯಾಶ್ ಟೇಬಲ್‌ನಲ್ಲಿ ಕೀ ಜೊತೆಗೆ ಅರ್ [ಐ] + ಆರ್ [ಜೆ] ಎಂದು ಇರಿಸಿ.
  2. ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯನ್ನು ನೀಡಲಾಗಿದೆ, ಅದು ಶ್ರೇಣಿಯಲ್ಲಿ ನಾಲ್ಕು ಅಂಶಗಳಿವೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಲು ಕೇಳುತ್ತದೆ, ಅದು ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯವನ್ನು ಒಟ್ಟುಗೂಡಿಸುತ್ತದೆ. ಹೌದು, ನಂತರ ಅನುಸರಿಸಿ ನಂತರ ಕಾರ್ಯವು ಹೌದು ಎಂದು ಮುದ್ರಿಸಬೇಕು, ಇಲ್ಲದಿದ್ದರೆ ಇಲ್ಲ ಎಂದು ಮುದ್ರಿಸಿ. ನಾವು ಬಳಸಲಿದ್ದೇವೆ ಹ್ಯಾಶಿಂಗ್ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು. ಆ ಕಾರಣದಿಂದಾಗಿ, ನಾವು ಕೀಲಿಯನ್ನು ನಮ್ಮ ಅಂಶವಾಗಿ ಸಂಗ್ರಹಿಸಬಹುದು, ಅದು ಸಂಭವನೀಯ ಉಪ-ರಚನೆಯಾಗಿ ಜೋಡಿಸುತ್ತದೆ ಮತ್ತು ಅದರ ಸೂಚ್ಯಂಕಗಳಂತೆ ಮೌಲ್ಯವನ್ನು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು.

ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸೋಣ:

ಉದಾಹರಣೆ

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, ಮೊತ್ತ = 25

ಇಲ್ಲಿ ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ತೆಗೆದುಕೊಂಡಿದ್ದೇವೆ. ನಾವು ಎ ಬೂಲಿಯನ್ ನಿಜವಾದ ಮತ್ತು ಸುಳ್ಳನ್ನು ಹಿಂದಿರುಗಿಸುವ ಕಾರ್ಯ. ನಮ್ಮ ನಕ್ಷೆಯಲ್ಲಿ, ನಾವು ಬಳಸಬೇಕಾದ ವಸ್ತುಗಳ ಆಬ್ಜೆಕ್ಟ್ ಆಸ್ತಿಯನ್ನು ಸಹ ನಾವು ಬಳಸಲಿದ್ದೇವೆ, ಏಕೆಂದರೆ ನಮ್ಮ ವಾದಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಪಟ್ಟಿ ಅಥವಾ ವೆಕ್ಟರ್ ಆಗಿದೆ. ಆದ್ದರಿಂದ ಮೂಲಭೂತವಾಗಿ ನಾವು ಅರೇಗಳನ್ನು ಹಾದುಹೋಗಲು ಹೋಗುತ್ತೇವೆ, ಆದರೆ ಒಂದು ಶ್ರೇಣಿಯ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ಹೊರಗಿನ ಲೂಪ್‌ನಲ್ಲಿ ತೆಗೆದುಕೊಂಡು ಎರಡನೇ ಒಳಗಿನ ಲೂಪ್‌ನೊಂದಿಗೆ ಒಂದು ಸೂಚ್ಯಂಕ ಮುಂದೆ ಬರುವ ಉಳಿದ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ.

ನಾವು arr [i] + arr [j] ಆಗಿರುವ ಎರಡೂ ಅಂಶಗಳ ಮೊತ್ತವನ್ನು ತೆಗೆದುಕೊಂಡು ಅದನ್ನು ವಾಲ್ ಎಂಬ ಕೆಲವು ವೇರಿಯೇಬಲ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ ನಂತರ ಮೊತ್ತ-ಮೌಲ್ಯವು ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ ಹ್ಯಾಶ್ಟೇಬಲ್ ಅಥವಾ ಇಲ್ಲದಿದ್ದರೆ, ಅಂಶಗಳನ್ನು ನಕ್ಷೆಗೆ ತಳ್ಳಿರಿ, ನಾವು ರಚನೆಯ ಅಂಶ 2 ಮತ್ತು 7 ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ (arr [i] ಮತ್ತು arr [j]) ಪಡೆಯುವ ಮೊತ್ತ 9 ಮತ್ತು 25-9 ಆಗಿರುವ ಮೊತ್ತ-ಮೌಲ್ಯ 18 ಆಗಿದೆ ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ ಇರುವುದಿಲ್ಲ, ಆದ್ದರಿಂದ ನಾವು 9 ಮತ್ತು ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕಗಳನ್ನು 0 ಮತ್ತು 1 ಎಂದು ಸರಳವಾಗಿ ತಳ್ಳುತ್ತೇವೆ, ಇದರಿಂದಾಗಿ ಮೊತ್ತ-ಅರ್ [i] + ಅರ್ [ಜೆ] ಟೇಬಲ್‌ನಲ್ಲಿ ಇದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ನಾವು ನಂತರ ಕಂಡುಹಿಡಿಯಬಹುದು. ಇದ್ದರೆ, ನಂತರ ಕೀಲಿಯ ಮೌಲ್ಯಗಳನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಅದರ ಮೇಲೆ ಕೆಲವು ಷರತ್ತುಗಳನ್ನು ಪರಿಶೀಲಿಸಿ, ಅದು ತೃಪ್ತಿ ಹೊಂದಿದ್ದರೆ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ. ಇದರರ್ಥ ನಾವು ನಮ್ಮ ಉತ್ತರವನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ.

ನಿರ್ದಿಷ್ಟ ಮೌಲ್ಯಕ್ಕೆ (ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್) ಒಟ್ಟು ನಾಲ್ಕು ಅಂಶಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಬಳಸುವುದರಿಂದ ಈ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸಾಧಿಸಲು ನಮಗೆ ಅವಕಾಶ ಮಾಡಿಕೊಟ್ಟಿತು, ಇಲ್ಲದಿದ್ದರೆ ಅದು ಸಾಧ್ಯವಾಗುತ್ತಿರಲಿಲ್ಲ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್2ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ N ^ 2 ಜೋಡಿಗಳು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಬೇಕಾಗಬಹುದು. ಹೀಗಾಗಿ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.