ຊອກຫາສີ່ອົງປະກອບທີ່ສົມກັບມູນຄ່າທີ່ໄດ້ຮັບ (Hashmap)


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon ກູໂກ Microsoft
Array Hash ຮຽງລໍາດັບ

ບັນຫາ "ຊອກຫາສີ່ອົງປະກອບທີ່ສົມກັບມູນຄ່າທີ່ໄດ້ຮັບ (Hashmap)" ກ່າວວ່າສົມມຸດວ່າທ່ານມີຕົວເລກເຕັມແລະຕົວເລກທີ່ເອີ້ນວ່າ sum. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ ກຳ ນົດວ່າສີ່ອົງປະກອບທີ່ມີຢູ່ໃນແຖວເຊິ່ງລວມເຖິງມູນຄ່າທີ່ຖືກມອບໃຫ້ເປັນ "ຜົນບວກ". ຖ້າຫາກວ່າແມ່ນ, ຫຼັງຈາກນັ້ນຜົນໄດ້ຮັບຜົນໄດ້ຮັບ "ແມ່ນແລ້ວ", ຜົນໄດ້ຮັບອື່ນໆ "ບໍ່".

ຍົກຕົວຢ່າງ

ຊອກຫາສີ່ອົງປະກອບທີ່ສົມກັບມູນຄ່າທີ່ໄດ້ຮັບ (Hashmap)

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. ເກັບຮັກສາມູນຄ່າຂອງ arr [i] + arr [j] ກັບ val ແລະກວດເບິ່ງວ່າ sum-val ມີຢູ່ໃນຕາຕະລາງ hash.
        1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນເອົາກຸນແຈແລະຊອກຫາເລກ, ແລະກັບຄືນມາເປັນຈິງ.
      2. ອີກອັນ ໜຶ່ງ, ເອົາໃສ່ i ແລະ j ເຂົ້າໄປໃນຕາຕະລາງ hash ພ້ອມກັບກະແຈທີ່ມາຮອດ as [i] + arr [j].
  2. ສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ ຄຳ ຖະແຫຼງທີ່ມີບັນຫາເຊິ່ງຖາມເພື່ອ ກຳ ນົດວ່າມັນມີສີ່ອົງປະກອບທີ່ມີຢູ່ໃນແຖວທີ່ສະຫຼຸບມູນຄ່າທີ່ໄດ້ໃຫ້ໄວ້ຫຼືບໍ່. ຖ້າມີ, ຫຼັງຈາກນັ້ນປະຕິບັດຕາມຫຼັງຈາກນັ້ນ ໜ້າ ທີ່ຄວນຈະພິມແມ່ນ, ບໍ່ແມ່ນພິມອື່ນ. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ ເຮື້ອຮັງ ເພື່ອແກ້ໄຂບັນຫານີ້. ຍ້ອນສິ່ງນັ້ນ, ພວກເຮົາສາມາດເກັບກຸນແຈເປັນສ່ວນປະກອບຂອງພວກເຮົາເຊິ່ງຈັບຄູ່ກັນເພື່ອເປັນແຖວຍ່ອຍທີ່ເປັນໄປໄດ້, ແລະມີຄ່າເປັນດັດຊະນີຂອງພວກເຮົາເພື່ອໃຫ້ພວກເຮົາສາມາດກວດສອບມັນໄດ້

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, ຜົນບວກ = 25

ນີ້ພວກເຮົາໄດ້ຍົກຕົວຢ່າງ. ພວກເຮົາໄດ້ປະກາດເປັນ ບົວບານ ຫນ້າທີ່ທີ່ຈະກັບຄືນມາເປັນຄວາມຈິງແລະບໍ່ຖືກຕ້ອງ. ໃນແຜນທີ່ຂອງພວກເຮົາ, ພວກເຮົາ ກຳ ລັງຈະ ນຳ ໃຊ້ຊັບສິນຂອງວັດຖຸທີ່ພວກເຮົາ ກຳ ລັງຈະ ນຳ ໃຊ້, ໃນທີ່ ໜຶ່ງ ຂອງການໂຕ້ຖຽງຂອງພວກເຮົາແມ່ນບັນຊີລາຍຊື່ຫລື vector. ສະນັ້ນໂດຍພື້ນຖານແລ້ວພວກເຮົາ ກຳ ລັງຈະຂຍາຍອາຄານ, ແຕ່ຖືເອົາແຕ່ລະອົງປະກອບຂອງອາເລໃນເວລາດຽວກັນໃນວົງນອກແລະຜ່ານສ່ວນທີ່ເຫຼືອຂອງອົງປະກອບທີ່ເຂົ້າມາດັດສະນີຂ້າງ ໜ້າ, ດ້ວຍວົງແຫວນພາຍໃນສອງ.

ພວກເຮົາເອົາຜົນລວມຂອງທັງສອງອົງປະກອບທີ່ມາຮອດ [i] + arr [j] ແລະເກັບມັນໄວ້ໃນບາງຕົວປ່ຽນທີ່ເອີ້ນວ່າ val ແລະຫຼັງຈາກນັ້ນກວດເບິ່ງວ່າ sum-val ມີຢູ່ໃນ hashtable ຫລືບໍ່, ຖ້າບໍ່ປະຈຸບັນກໍ່ພຽງແຕ່ຍູ້ອົງປະກອບເຂົ້າໄປໃນແຜນທີ່, ສົມມຸດວ່າພວກເຮົາມີທາດຂອງອົງປະກອບ 2 ແລະ 7 (arr [i] ແລະ arr [j]) ໄດ້ຮັບຜົນລວມແມ່ນ 9 ແລະ sum-val ທີ່ 25-9 ແມ່ນ 18 ແມ່ນ ບໍ່ສະແດງຢູ່ໃນຕາຕະລາງ hash, ດັ່ງນັ້ນພວກເຮົາກົດດັນ 9 ແລະດັດສະນີດັດສະນີທີ່ເປັນ 0 ແລະ 1, ເພື່ອວ່າໃນພາຍຫລັງພວກເຮົາຈະຮູ້ວ່າ sum-arr [i] + arr [j] ມີຢູ່ຫລືບໍ່ຢູ່ໃນຕາຕະລາງ. ຖ້າມີໃນປະຈຸບັນ, ຫຼັງຈາກນັ້ນພຽງແຕ່ໄດ້ຮັບຄຸນຄ່າຂອງຄີແລະກວດເບິ່ງບາງເງື່ອນໄຂກ່ຽວກັບມັນ, ຖ້າມັນພໍໃຈແລ້ວກໍ່ກັບມາເປັນຄວາມຈິງ. ມັນ ໝາຍ ຄວາມວ່າພວກເຮົາພົບ ຄຳ ຕອບຂອງພວກເຮົາ.

ລະຫັດ C ++ ເພື່ອຊອກຫາສີ່ອົງປະກອບທີ່ບວກກັບມູນຄ່າທີ່ໄດ້ຮັບ (Hashmap)

#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

ລະຫັດ Java ເພື່ອຊອກຫາສີ່ອົງປະກອບທີ່ບວກກັບມູນຄ່າທີ່ໄດ້ຮັບ (Hashmap)

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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ການໃຊ້ HashMap ຊ່ວຍໃຫ້ພວກເຮົາປະສົບກັບຄວາມຫຍຸ້ງຍາກໃນຊ່ວງເວລານີ້ອີກບໍ່ແມ່ນວ່າມັນຈະເປັນໄປໄດ້.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (ນ2ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດອາດຈະມີ N ^ 2 ຄູ່ທີ່ຕ້ອງການເກັບຮັກສາໄວ້ໃນແຜນທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນມີຫຼາຍຮູບແບບ.