ספרו זוגות משני מערכים ממוינים שסכומם שווה לערך נתון x  


רמת קושי קַל
נשאל לעתים קרובות בנק בזאר סיסקו מצודה Honeywell PayU רובלוקס Taxi4Sure Yandex
מערך בליל מִיוּן STL

הצהרת בעיה  

"ספר זוגות משניים מיון מערכים שסכומם שווה לערך נתון x "בעיה קובעת כי ניתנים לך שני מערכים ממוינים של מספרים שלמים וערך שלם הנקרא סכום. הצהרת הבעיה מבקשת לברר את המספר הכולל של הצמד שמסתכם בערך נתון.

דוגמה  

arr1[] = {1, 6, 8, 11}

arr2[] = {1, 3, 5, 9}

sum = 9
2

 

הסבר: מכיוון שיש בסך הכל 2 זוגות במערך נתון שהוא (6, 3) ו- (8, 1). מכיוון שלזוגות אחרים סכום גדול או פחות מהסכום הנדרש.

arr1[] = {3, 5, 11, 14};

arr2[] = {2, 4, 5, 11}

sum = 16
3

 

הסבר: מכיוון שיש בסך הכל 3 זוגות במערך הנתון שהם (5, 11), (11, 5) ו- (14, 2).

אלגוריתם לספירת זוגות משני מערכים ממוינים שסכומם שווה לערך נתון x  

1. Set count and left to 0, and right to n-1 where n is the length of the array.
2. While left is less than m and right is greater than equal to 0, repeat the following the steps-
    1. If the sum of arr[left] and arr[right] is equal to the given value, then increase the value of count and left by 1 and decrease the value of right by 1.
    2. Else check if the addition of arr[left] and arr[right] is less than the given value sum, then increase the value of left by 1.
    3. Decrease the value of right by 1 if the addition is greater than the sum.
3. Return the count value after traversing the arrays.

הסבר

מקבלים שני מספרים שלמים ממוינים מערכים וערך שלם הנקרא סכום. ונבקש לברר כמה זוגות אפשריים יכולים להיווצר המסכמים לערך נתון. לכן, אנו הולכים להשתמש בטכניקה דומה כשיטת חיפוש בינארית. זו גם הסיבה שאנחנו לוקחים ערכי קלט בסדר הולך וגדל. בדרך זו נוכל ליישם את הטכניקה הזו בפתרון שאלה זו. אחרת היינו ממיינים את המערך.

ראה גם
פתרון Leetcode של מערכת חניה מעוצבת

אנחנו הולכים לקבוע את הערך של לספור ל- 0. מכיוון שנעלה את ערך הספירה ב -1 אם נמצא את הזוג הנדרש. זוג יורכב משני ערכים. כמובן, אנו הולכים לבדוק אם תוספת ערך זה בזוג שווה לסכום הערך הנתון. אם זה נכון נגדיל את ערך הספירה ב- 1. נפעיל a תוך לולאה באופן זה. ואז זה ילך עד שהערכים m (m הם אורכו של אחד המערכים) ו- r (כאשר r הוא אחד פחות מאורכו של מערך) גדול משווה ל- 0.

בלולאה, נבדוק אם ערך הצמד מצטבר לערך הנתון. לאחר מכן מצאנו זוג אחד בכל פעם שמצב זה מתממש. נמשיך בלולאה אם ​​הסכום נמוך מהערך הנתון. ואז נגדיל את הערך של l ב -1 אחר אנחנו פשוט מורידים את הערך של r עד 1. בסופו של דבר נחזיר את ערך הספירה.

ספרו זוגות משני מערכים ממוינים שסכומם שווה לערך נתון xאורן

קופונים  

קוד C ++ לספירת זוגות שסכומם x משני מערכים ממוינים

#include<iostream>

using namespace std;

int getPairofsum(int arr1[], int arr2[], int m, int n, int sum)
{
    int count = 0;
    int left = 0, right = n - 1;

    while (left < m && right >= 0)
    {
        if ((arr1[left] + arr2[right]) == sum)
        {
            left++;
            right--;
            count++;
        }
        else if ((arr1[left] + arr2[right]) < sum)
            left++;
        else
            right--;
    }
    return count;
}
int main()
{
    int arr1[] = {1, 6, 8, 11};
    int arr2[] = {1, 3, 5, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    int sum = 9;
    cout << "Count = "<< getPairofsum(arr1, arr2, m, n, sum);
    return 0;
}
Count = 2

 

ראה גם
שאילתות סכום טווח ללא עדכונים

קוד Java כדי לספור זוגות שסכומם x משני מערכים ממוינים

class PairofSum
{
    public static int getPairofsum(int arr1[],int arr2[], int m, int n, int sum)
    {
        int count = 0;
        int left = 0, right = n - 1;

        while (left < m && right >= 0)
        {
            if ((arr1[left] + arr2[right]) == sum)
            {
                left++;
                right--;
                count++;
            }
            else if ((arr1[left] + arr2[right]) < sum)
                left++;
            else
                right--;
        }
        return count;
    }
    public static void main (String[] args)
    {
        int arr1[] = {1, 6, 8, 11};
        int arr2[] = {1, 3, 5, 9};
        int m = arr1.length;
        int n = arr2.length;
        int sum = 9;
        System.out.println( "Count = "+ getPairofsum(arr1, arr2, m, n, sum));
    }
}
Count = 2

 

ניתוח מורכבות  

מורכבות זמן

O (m + n) איפה "M" ו "N" הוא מספר האלמנטים ב- arr1 ו- arr2. מכיוון שהמקסימום שנוכל לנסוע הוא m + n.

מורכבות בחלל

O (1) מכיוון שלא נדרש מקום נוסף. כך מושגת מורכבות חלל קבועה.