מצא את כל זוגות המספרים במערך המסתכם בסכום נתון בג'אווה

1. סקירה כללית

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

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

עבור כל גישה נציג שתי יישומים - יישום מסורתי באמצעות ל לולאות ושנייה באמצעות Java 8 Stream API.

2. החזר את כל הזוגות התואמים

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

לצורך ההפגנות שלנו, נחפש את כל זוגות המספרים שסכומם שווה ל- 6, באמצעות הדברים הבאים קֶלֶט מַעֲרָך:

int [] קלט = {2, 4, 3, 3}; 

בגישה זו, האלגוריתם שלנו אמור להחזיר:

{2,4}, {4,2}, {3,3}, {3,3}

בכל אחד מהאלגוריתמים, כאשר אנו מוצאים צמד מספרים של יעדים המסכמים למספר היעד, אנו אוספים את הצמד בשיטת כלי עזר, addPairs (i, j).

הדרך הראשונה בה אנו עשויים לחשוב ליישם את הפתרון היא באמצעות המסורתית ל לוּלָאָה:

עבור (int i = 0; i <input.length; i ++) {for (int j = 0; j <input.length; j ++) {if (j! = i && (קלט [i] + קלט [j]) == סכום) {addPairs (קלט [i], סכום קלט [i])); }}}

זה יכול להיות קצת ראשוני, אז בואו גם נכתוב יישום באמצעות Java 8 Stream API.

כאן אנו משתמשים בשיטה IntStream.range כדי ליצור זרם רציף של מספרים. לאחר מכן אנו מסננים אותם למצבנו: מספר 1 + מספר 2 = סכום:

IntStream.range (0, input.length) .forEach (i -> IntStream.range (0, input.length). Filter (j -> i! = J && input [i] + input [j] == sum) .forEach (j -> addPairs (קלט [i], קלט [j]))); 

3. החזר את כל הזוגות התואמים הייחודיים

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

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

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

{2,4}, {3,3}

אם אנו משתמשים במסורת ל לולאה, יהיה לנו:

זוגות מפה = HashMap חדש (); עבור (int i: קלט) {if (pairs.containsKey (i)) {if (pairs.get (i)! = null) {addPairs (i, sum-i); } pairs.put (סכום - i, null); } אחר אם (! pairs.containsValue (i)) {pairs.put (sum-i, i); }}

שים לב כי יישום זה משפר את המורכבות הקודמת, כמו אנו משתמשים רק באחד ל לולאה, כך שיהיה לנו עַל).

בואו נפתור את הבעיה באמצעות Java 8 ו- Stream API:

זוגות מפה = HashMap חדש (); IntStream.range (0, input.length) .forEach (i -> {if (pairs.containsKey (input [i]))) {if (pairs.get (input [i])! = Null) {addPairs (input [ i], sum - input [i]);} pairs.put (sum - input [i], null);} else if (! pairs.containsValue (input [i])) {pairs.put (sum - input [ i], קלט [i]);}});

4. מסקנה

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

כרגיל, את כל דגימות הקוד המוצגות במאמר זה ניתן למצוא ב- GitHub - זהו פרויקט של Maven, כך שיהיה קל להרכיבו ולהריצו.


$config[zx-auto] not found$config[zx-overlay] not found