ספירת זוגות עם סכום נתון


רמת קושי קַל
נשאל לעתים קרובות נאמן אמזון בעברית סט עובדות טיול
מערך בליל מתמטיקה מִיוּן

ניתן מספר שלם מערך בגודל n ומספר שלם 'K', עליך לספור את מספר הזוגות (לא צריך להיות ייחודי) הקיים במערך שסכומו שווה ל- 'K'.

דוגמה

קלט:

Arr = {1, 5, 7, 1}

K = 6

פלט:

2

פתרון כוח אכזרי לספירת זוגות עם סכום נתון

רעיון מרכזי

אנו יכולים לחזור על כל זוגות המערך הנתון, ואז לספור את הזוגות שסכומם שווה ל- K.

אַלגוֹרִיתְם

  1. אתחל תשובה משתנה = 0.
  2. הפעל לולאה עבור אני בטווח 0 עד n-1
    1. הפעל לולאה עבור j בטווח i + 1 עד n-1;
      1. אם arr [i] + arr [j] שווה ל- k, אז תשובת הגדלה ב -1.
  3. השיב תשובה.

יישום

תוכנית C ++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]+a[j]==k){
                ans++;
            }
        }
    }
    cout<<"Number of pairs with the given sum are: "<<ans;
}
4 6
1  5  7 1
Number of pairs with the given sum are: 2

תוכנית JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]+a[j]==k){
                    ans++;
                }
            }
        }
    System.out.println("Number of pairs with the given sum are: "+ans);
  }
}

6 4
2 2 3 1 1 5
Number of pairs with the given sum are: 3

ניתוח מורכבות לספירת זוגות עם סכום נתון

מורכבות זמן

כשאנחנו חוזרים על כל הזוגות ויש בערך N ^ 2 זוגות, כך מורכבות הזמן הכוללת היא O (N ^ 2).

מורכבות חלל

לא השתמשנו בשום שטח נוסף ולכן מורכבות החלל היא O (1).

רעיון Hashing לספירת זוגות עם סכום נתון

רעיון מרכזי

אנו נשמור על טבלת hash אשר תאחסן את התדירות של כל מספר במערך הנתון.

כעת נחזור על המערך ונוסיף את כל האלמנטים שערכם שווה ל- k-arr [i].

אבל עלינו לבדוק תנאי אחד:

אם arr [i] שווה ל- k-arr [i], אז נפחית 1 מהתשובה שלנו מכיוון שעלינו למצוא זוגות מובחנים, ולכן איננו יכולים לקחת arr [i] פעמיים לזוג, לכן נגרע מקרה מתשובתנו.

אַלגוֹרִיתְם

  1. הכינו טבלת hash שתאחסן את ספירת כל אלמנט במערך.
  2. מחזירים את המערך עבור I בטווח 0 עד n-1
    1. אם arr [i] שווה ל- k-arr [i], הוסף (count_of (k-arr [i]) - 1) לתשובה.
    2. אם arr [i] אינו שווה ל- k-arr [i], ואז הוסף (count_of (k-arr [i]) לתשובה.
  3. השיב תשובה.

דוגמה

טבלת האש שנוצרה עבור המערך = {1, 2, 3, 3, 4, 1, 1} היא:

ספירת זוגות עם סכום נתון

יישום

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> fre;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        fre[arr[i]]++;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == k - arr[i])
        {
            answer += (fre[arr[i]] - 1);
        }
        else
        {
            answer += (fre[k - arr[i]]);
        }
    }
    answer /= 2;
    cout << "Number of pairs with the given sum are: "<<answer << endl;
    return 0;
}
6 4
1 2 2 2 3 4
Number of pairs with the given sum are: 4

תוכנית JAVA

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            Integer j = fre.get(arr[i]); 
            fre.put(arr[i], (j == null) ? 1 : j + 1); 
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == k - arr[i])
            {
                answer += (fre.get(arr[i]) - 1);
            }
            else
            {
                Integer j = fre.get(k - arr[i]); 
                if(j!=null)
                    answer += j;
            }
        }
        answer /= 2;
    System.out.println("Number of pairs with the given sum are: "+answer);
  }
}

6 7
3 5 6 1 4 4
Number of pairs with the given sum are: 3

ניתוח מורכבות לספירת זוגות עם סכום נתון

מורכבות זמן

אנו חוזרים על המערך פעם אחת בלבד, ולכן מורכבות הזמן היא O (N).

מורכבות חלל

אנו שומרים על שולחן חשיש, ולכן מורכבות החלל שלנו היא O (N).

הפניות