ນັບຄູ່ກັບ Given Sum


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon ປັດໃຈ hike
Array ແຮກ ຄະນິດສາດ ຮຽງລໍາດັບ

ໃນບັນຫາ“ ນັບຄູ່ກັບຍອດລວມ” ພວກເຮົາໄດ້ເອົາເລກເຕັມ array[] ແລະອີກຕົວເລກ ໜຶ່ງ ເວົ້າວ່າ 'ລວມ', ທ່ານຕ້ອງ ກຳ ນົດວ່າສອງໃນສອງອົງປະກອບໃດ ໜຶ່ງ ໃນແຖວໃດ ໜຶ່ງ ມີ ຈຳ ນວນເທົ່າກັບ "ຜົນບວກ".

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

arr [] = {1,3,4,6,7} ແລະຜົນບວກ = 9.

ຜົນໄດ້ຮັບ:

ອົງປະກອບທີ່ພົບເຫັນ ຜົນບວກ” ຍ້ອນວ່າມີ '3' ແລະ '6' ເຊິ່ງມີຜົນລວມເທົ່າກັນ ເຖິງ '9'.

ການປ້ອນຂໍ້ມູນ:

arr [] = {11,3,5,7,10} ແລະຜົນບວກ = 20.

ຜົນໄດ້ຮັບ:

“ ສ່ວນປະກອບທີ່ບໍ່ພົບກັບ ຈຳ ນວນທີ່ໃຫ້ໄວ້” ຍ້ອນວ່າບໍ່ມີຕົວເລກໃດ ໜຶ່ງ ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 8

ລະບົບວິເຄາະ

  1. ປະກາດກ ທີ່ກໍານົດໄວ້.
  2. ໃນຂະນະທີ່ 0 ເຖິງ 'i' ແມ່ນຫນ້ອຍກ່ວາຄວາມຍາວຂອງອາເລ.
    1. ຕັ້ງ j ເພື່ອ sum-arr [i].
    2. ກວດເບິ່ງວ່າຊຸດທີ່ມີ 'j', ຖ້າແມ່ນຂອງແທ້ພິມແລ້ວ j ແລະມາຮອດ [i], ນີ້ແມ່ນຄູ່.
    3. ອື່ນຕື່ມການເຂົ້າ [i] ເຂົ້າໃນຊຸດ.

ຄໍາອະທິບາຍ

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

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

ເພື່ອຄົ້ນຫາມັນ, ພວກເຮົາຈະ ນຳ ໃຊ້ວິທີການທີ່ຫຍຸ້ງຍາກ.

ຂໍໃຫ້ເຮົາຍົກຕົວຢ່າງ:

arr [] = {1, 4, 45, 6, 10, 8};

  • i = 0, myset, ຜົນບວກ = 16;

j = sum-arr [i];

ນັ້ນແມ່ນ j = 16-1 = 15 ແລະແນ່ນອນ 'j' ຈະບໍ່ມີຢູ່ໃນແຜນທີ່.

ສະນັ້ນມັນຈຶ່ງເພີ່ມເຂົ້າ [i] ນັ້ນແມ່ນ '1' ເຂົ້າໃນ myset.

  • i = 1, myset = {1}, ຜົນບວກ = 16;

j = sum-arr [i];

ນັ້ນແມ່ນ j = 16-4 = 12 ແລະແນ່ນອນ 'j' ແມ່ນບໍ່ມີຢູ່ໃນແຜນທີ່.

ສະນັ້ນມັນຈຶ່ງເພີ່ມເຂົ້າ [i] ນັ້ນແມ່ນ '4' ເຂົ້າໃນ myset.

  • i = 2, myset = {1, 4}, ຜົນບວກ = 16;

j = sum-arr [i];

ນັ້ນແມ່ນ j = 16-45 = -29 ແລະແນ່ນອນ 'j' ຈະບໍ່ຢູ່ໃນແຜນທີ່.

ສະນັ້ນມັນຈຶ່ງເພີ່ມເຂົ້າ [i] ນັ້ນແມ່ນ '45' ເຂົ້າໃນ myset.

  • i = 3, myset = {1, 4, 45}, ຜົນບວກ = 16;

j = sum-arr [i];

ນັ້ນແມ່ນ j = 16-6 = 10 ແລະ j ບໍ່ມີຢູ່ໃນແຜນທີ່.

ສະນັ້ນມັນຈຶ່ງເພີ່ມເຂົ້າ [i] ນັ້ນແມ່ນ '6' ເຂົ້າໃນ myset.

  • i = 4, myset = {1, 4, 45, 6}, ຜົນບວກ = 16;

j = sum-arr [i];

ນັ້ນແມ່ນ j = 16-10 = 6 ແລະ j ແມ່ນມີຢູ່ໃນແຜນທີ່.

ນີ້ແມ່ນບ່ອນທີ່ພວກເຮົາພົບເຫັນຄູ່ຂອງຄູ່ອີກຄູ່ ໜຶ່ງ. ພວກເຮົາໄດ້ປະຕິບັດງານແລ້ວໃນວັນທີ 16 ແລະ 10.

ແລະພວກເຮົາພິມ:

“ ພົບເຫັນອົງປະກອບທີ່ມີຄ່າລວມເປັນ 16, ແມ່ນ (10, 6);

ນັ້ນ ໝາຍ ຄວາມວ່າສອງອົງປະກອບມີຢູ່ໃນແຖວເຊິ່ງມີຜົນບວກເທົ່າກັບ“ ຜົນບວກ”.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບ Count ຄູ່ກັບ Given Sum

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}
Found elements with the given sum as 16 is (10, 6)

ໂປແກຼມ Java ສຳ ລັບ Count pair ກັບ Given Sum

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບຄູ່ທີ່ມີລວມຍອດ

ຄວາມສັບສົນເວລາ

O (n) ຍ້ອນວ່າຂບວນການທັງ ໝົດ ແມ່ນ ຈຳ ເປັນທີ່ຈະຕ້ອງໄດ້ຜ່ານຜ່າພຽງຄັ້ງດຽວ.

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

O (n) ຍ້ອນວ່າແຜນທີ່ hash ໄດ້ຖືກ ນຳ ໃຊ້ເພື່ອຈັດເກັບອົງປະກອບຕ່າງໆ.

ກະສານອ້າງອີງ