นับคู่กับผลรวมที่ได้รับ


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ อเมซอน ข้อเท็จจริง ธุดงค์
แถว hashing คณิตศาสตร์ การเรียงลำดับ

ในปัญหา "นับคู่กับผลรวมที่กำหนด" เราได้ให้จำนวนเต็ม แถว[] และอีกจำนวนหนึ่งพูดว่า 'ผลรวม' คุณต้องพิจารณาว่าองค์ประกอบใดในสององค์ประกอบในอาร์เรย์หนึ่ง ๆ มีผลรวมเท่ากับ "ผลรวม" หรือไม่

ตัวอย่าง

Input:

arr [] = {1,3,4,6,7} และ sum = 9

Output:

“ องค์ประกอบที่พบในสิ่งที่กำหนด sum” เนื่องจากมี '3' และ '6' ซึ่งมีผลรวมเท่ากัน ถึง '9'

Input:

arr [] = {11,3,5,7,10} และ sum = 20

Output:

“ ไม่พบองค์ประกอบในผลรวมที่กำหนด” เนื่องจากไม่มีตัวเลขใด ๆ ที่มีผลรวมเท่ากับ '8'

ขั้นตอนวิธี

  1. ประกาศก ชุด.
  2. ในขณะที่ 0 ถึง 'i' น้อยกว่าความยาวของอาร์เรย์
    1. ตั้งค่า j เป็น sum-arr [i]
    2. ตรวจสอบว่าชุดมี 'j' หรือไม่ถ้าเป็นจริงจากนั้นพิมพ์ j และ arr [i] ซึ่งจะเป็นคู่
    3. เพิ่ม arr [i] เข้าไปในชุด

คำอธิบาย

เราได้ให้คำชี้แจงปัญหาซึ่งเราได้รับอาร์เรย์จำนวนเต็มและตัวเลขพูดว่า 'ผลรวม' งานของเราคือการพิจารณาว่าอาร์เรย์มีองค์ประกอบใด ๆ จากสององค์ประกอบที่มีผลรวมเท่ากับ "ผลรวม" ที่กำหนดหรือไม่

แนวคิดหลักของเราคือการใช้ HashSet และค้นหาคู่ ซึ่งเราจะเก็บความแตกต่างของผลรวมและแต่ละค่าของอาร์เรย์ในขณะที่เคลื่อนที่เนื่องจากคู่หนึ่งมีองค์ประกอบทั้งสองนั้นและผลรวมที่กำหนดเป็นกุญแจสำคัญในการค้นหาองค์ประกอบอื่นนั่นคือเหตุผลที่เราเก็บองค์ประกอบอาร์เรย์ทั้งหมดไว้ในชุด และพิจารณาดูว่ามีองค์ประกอบใดองค์ประกอบหนึ่งในคู่หรือไม่

หากต้องการทราบเราจะใช้วิธีการแฮช

ให้เรายกตัวอย่าง:

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

  • ผม = 0, myset, sum = 16;

j = sum-arr [i];

นั่นคือ j = 16-1 = 15 และแน่นอนว่า 'j' จะไม่ปรากฏในแผนที่

ดังนั้นมันจึงเพิ่ม arr [i] นั่นคือ '1' เข้าไปใน myset

  • ผม = 1, myset = {1}, sum = 16;

j = sum-arr [i];

นั่นคือ j = 16-4 = 12 และแน่นอนว่า 'j' ไม่มีอยู่ในแผนที่

ดังนั้นมันจึงเพิ่ม arr [i] นั่นคือ '4' เข้าไปใน myset

  • ผม = 2, myset = {1, 4}, sum = 16;

j = sum-arr [i];

นั่นคือ j = 16-45 = -29 และแน่นอนว่า 'j' จะไม่อยู่ในแผนที่

ดังนั้นมันจึงเพิ่ม arr [i] นั่นคือ '45' เข้าไปใน myset

  • ผม = 3, myset = {1, 4, 45}, sum = 16;

j = sum-arr [i];

นั่นคือ j = 16-6 = 10 และ j ไม่มีอยู่ในแผนที่

ดังนั้นมันจึงเพิ่ม arr [i] นั่นคือ '6' เข้าไปใน myset

  • ผม = 4, myset = {1, 4, 45, 6} ผลรวม = 16;

j = sum-arr [i];

นั่นคือ j = 16-10 = 6 และ j มีอยู่ในแผนที่

นี่คือที่ที่เราพบองค์ประกอบของคู่อื่น เราได้ดำเนินการไปแล้วเมื่อวันที่ 16 และ 10

และเราพิมพ์:

“ พบองค์ประกอบที่มีผลรวมเป็น 16 คือ (10, 6);

นั่นหมายความว่ามีองค์ประกอบสององค์ประกอบอยู่ในอาร์เรย์ซึ่งมีผลรวมเท่ากับ“ ผลรวม”

การดำเนินงาน

โปรแกรม C ++ สำหรับ Count pair กับ 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 กับ 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) เนื่องจากมีการใช้แผนที่แฮชเพื่อจัดเก็บองค์ประกอบอาร์เรย์

การอ้างอิง