ပေးထားသော Sum နှင့်အတူစုံတွဲတစ်တွဲရေတွက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite အမေဇုံ အချက်အလက် ခရီးသွား
အခင်းအကျင်း တားဆီးခြင်း သင်္ချာ sorting

ပြproblemနာမှာ“ count pair with the sum” မှာကိန်းတစ်ခုပေးထားတယ် အခင်းအကျင်း[] နှင့်အခြားနံပါတ်တစ်ခုက 'sum' ဟုပြောပြီး၊ ပေးထားသောခင်းကျင်းထဲရှိဒြပ်စင်နှစ်ခုအနက်မှပေါင်းလဒ်သည် 'sum' နှင့်တူညီမှုရှိမရှိသင်ဆုံးဖြတ်ရန်ဖြစ်သည်။

နမူနာ

input:

arr [] = {1,3,4,6,7} နှင့်ပေါင်းလဒ် = 9 ။

output:

"ပေးထားသောနှင့်အတူတွေ့ရှိ Element တွေကို ပေါင်းလဒ်သည်ညီမျှသော '3' နှင့် '6' ရှိသဖြင့် '9' သို့။

input:

arr [] = {11,3,5,7,10} နှင့်ပေါင်းလဒ် = 20 ။

output:

'8' နှင့်ညီမျှသောမည်သည့်ဂဏန်းမျှမရှိသောကြောင့်“ ပေးထားသောပေါင်းလဒ်နှင့်မတွေ့ရသောဒြပ်စင်များ” ။

algorithm

  1. a) ကြေညာပါ အစုံ.
  2. 0 to 'i' သည် array ၏အရှည်ထက်နည်းနေစဉ်။
    1. sum ကို -rr [ဈ] မှည Set ။
    2. အစုံတွင် 'j' ပါမပါကိုစစ်ပါ။ အမှန်ဖြစ်ပါက j နှင့် arr [i] ကိုရိုက်ပါ၊ ၎င်းသည်အတွဲဖြစ်လိမ့်မည်။
    3. ကျန် arr သို့ [i] ကိုထည့်ပါ။

ရှင်းလင်းချက်

ကျွန်တော်တို့ကပြstatementနာကြေငြာချက်တစ်ခုကိုပေးထားတယ်။ အဲ့ဒီကိန်းဂဏန်းကိန်းဂဏန်းနဲ့ 'sum' လို့ခေါ်တယ်။ ကျွန်ုပ်တို့၏တာ ၀ န်မှာ ၀ တ္ထုနှစ်ခုသည်တစ်ခုခုကိုပေါင်းလျှင်“ sum” နှင့်တူညီသည်။

ကျွန်တော်တို့ရဲ့အဓိကအကြံဥာဏ်ကတော့ HashSet ကိုသုံးပြီးတစ်စုံရှာရန်ဖြစ်သည်။ အဘယ်ကြောင့်ကျွန်ုပ်တို့သည်ဖြတ်သန်းနေစဉ် sum ၏ခြားနားမှုနှင့် array ၏တန်ဖိုးတစ်ခုစီကိုသိမ်းဆည်းတော့မည်။ အဘယ်ကြောင့်ဆိုသော် pair တစုံတွင်၎င်းဒြပ်စင်နှစ်မျိုးရှိပြီးပေးထားသောပေါင်းလဒ်သည်အခြား element တစ်ခုကိုရှာရန်သော့ချက်ဖြစ်သည်။ pair တစုံထဲမှ element တစ်ခုသည်ပစ္စုပ္ပန်ဖြစ်စေမဖြစ်လျှင်၎င်းကိုကြည့်ပါ။

အဲဒါကိုရှာတွေ့ဖို့အတွက် hashing method ကိုကျွန်တော်တို့သုံးမယ်။

ဥပမာတစ်ခုယူကြစို့။

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

  • i = 0, myset, sum = 16;

ည = sum-arr [ဈ];

ဆိုလိုသည်မှာ j = 16-1 = 15 ဖြစ်ပြီး၊ 'j' သည်မြေပုံတွင်မရှိပါ။

ဒါကြောင့် arr [i] ကို '1' ​​ကို myset သို့ထည့်ပါ။

  • ဈ = 1, myset = {1}, ပေါင်းလဒ် = 16;

ည = sum-arr [ဈ];

ဆိုလိုသည်မှာည = 16-4 = 12 ဖြစ်ပြီးမြေပုံတွင် 'ည' မပါရှိပါ။

ဒါကြောင့် arr [i] ကို '4' ​​ကို myset သို့ထည့်ပါ။

  • ဈ = 2, myset = {1, 4}, ပေါင်းလဒ် = 16;

ည = sum-arr [ဈ];

ဆိုလိုသည်မှာည = 16-45 = -29 ဖြစ်ပြီး၊ 'j' သည်မြေပုံတွင်မရှိပါ။

ဒါကြောင့် arr [i] ကို '45' ​​ကို myset သို့ထည့်ပါ။

  • ကိုယ့် = 3, myset = {1, 4, 45}, ပေါင်းလဒ် = 16;

ည = sum-arr [ဈ];

ကြောင်းည = 16-6 = 10 ဖြစ်ပြီးညမြေပုံ၌မပါ။

ဒါကြောင့် arr [i] ကို '6' ​​ကို myset သို့ထည့်ပါ။

  • ဈ = 4, myset = {1, 4, 45, 6}, ပေါင်းလဒ် = 16;

ည = sum-arr [ဈ];

ကြောင်းည = 16-10 = 6 နှင့်ညမြေပုံ၌တည်ရှိ၏။

ဒီဟာကနောက်ထပ်စုံတွဲတစ်တွဲကိုရှာတွေ့တဲ့နေရာပဲ။ ကျနော်တို့ 16 နှင့် 10 ရက်နေ့တွင်စစ်ဆင်ရေးပြုပါပြီ။

ပြီးတော့ငါတို့ပုံနှိပ်တယ်။

"16 အဖြစ်ပေးထားသောပေါင်းလဒ်နှင့်အတူတွေ့ရှိရသောဒြပ်စင်, (10, 6) ဖြစ်၏

ဆိုလိုသည်မှာ element ၏နှစ်ခုသည်“ sum” နှင့်တူညီသည်။

အကောင်အထည်ဖော်ရေး

Count pair အတွက် C ++ ပရိုဂရမ်သည်ပေးထားသော 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)

Count pair အတွက် Java program

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)

Count pair တစုံအတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်းပေးထားသောပမာဏနှင့်ပေါင်းစပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (ဎ) တစ်ခုလုံးကိုခင်းကျင်းတစ်ချိန်ကသာဖြတ်သန်းရန်လိုအပ်ပါသည်အဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) တစ် ဦး hash မြေပုံအဖြစ်ခင်းကျင်းဒြပ်စင်သိမ်းဆည်းရန်အသုံးပြုခဲ့သည်။

အညွှန်း