Давши список 1, 4, 5, 9, 2 напишіть програму, щоб знайти можливі комбінації двох значень, коли сума = 6

Даний масив а = [1,4,5,9,2]. Мені потрібно знайти/роздрукувати комбінації з двох значень, коли сума = 6.

Мій код виглядає таким чином: (це O (n ^ 2), а не ефективне). Будь-які кращі рішення -

for(int out=0;out
3
Для малих N, 1) не має значення, чи рішення є ефективним, і 2) O (N ^ 2) може бути швидше, ніж O (N)
додано Автор Stephen C, джерело

3 Відповіді

  1. Помістіть всі числа в HashSet .
  2. Ітератуйте над масивом і для кожного елемента val перевірте, чи знаходиться HashSet 6-вал .

Я не показую код, оскільки це виглядає як домашня робота (якщо вона є, позначте її як таку).

Крім того, для коротких масивів рішення O (n ^ 2) майже напевно буде швидше, ніж це.

10
додано
Я можу підтвердити, що це досить стандартне питання інтерв'ю. Коли я проводив інтерв'ю, це сталося так само, як кожне з 1 з 5 інтерв'ю. Також ваша відповідь є кращою ... вона перетинає список лише два рази, що є O (n) рішенням.
додано Автор Nicholas, джерело
Дякую за відповідь Aix. Це не домашнє завдання. Шукаючи питання з інтерв'ю SD, я наткнувся на це питання. Тепер я додав тег "інтерв'ю".
додано Автор srock, джерело

По-перше, рішення, надане srock, має бути таким, як показано нижче

int length = a.length;

for(int out = 0; out < length ; out++) {
   for(int inn = 0; inn < length; inn ++) {
      if ((inn != out) && ((a[inn] + a[out]) == 6))
      sysout("The valid combination is "+a[inn]+" "+a[out])
   }
 }

І, звичайно, це потрібно повторити довжину * довжини разів. Як зазначалося в aix Якщо ми використовуємо Hashset з вмістом, то буде повторювати лише довжину не кількість разів і містить метод, який безпосередньо перейде до місця розміщення, використовуючи хеш-код, і буде завантажувати дані для порівняння. Таким чином, цей HashSet :: містить спосіб найкраще для великих без дат.

0
додано
for(int out=0;out
0
додано
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників