номера в массиве добавить к определенному номеру java

Question

Что является наиболее эффективным способом проверки, если любые числа в массиве суммируются до определенного числа, например: массив из (5,3,3,9,4) I хотите знать, можно ли добавить любое из этих чисел в массив, чтобы дать 10 , это произойдет, когда я добавлю (3,3,4)

Answer 1

Мне нужно было провести больше времени, чем сейчас, чтобы придумать с действительно хорошим решением, но я бы предложил пересмотреть вашу стратегию. Как упоминал @DeepakBala, вы описываете NP-полную проблему.

Одна вещь, которая делает это по-другому, состоит в том, что сумма (Q) может быть значительно больше, чем числа в массиве. Кроме того, поскольку они ограничены между 3 и 150, когда у вас 2000 номеров, у вас будет много дубликатов. Используйте это в своих интересах - подсчитывайте числа перед работой с ними, и вам нужно только беспокоиться о 149 типах чисел.

Чтобы вы могли подумать, почему это важно, рассмотрите сортировку 1 миллиона номеров 1-100. Просто создайте массив, а затем подсчитайте, сколько раз вы видите каждый номер. Затем заново создайте список, напечатав каждый номер соответствующим количеством раз. Это O (n) вместо нормального O (n log (n)).

Вместо того, чтобы работать с массивом до 2000 чисел, рассмотрите массивы 150, которые расскажут вам о том, сколько из каждого вашего размера доступно и сколько из каждого размера вы используете.

Попробуйте добавить все большие числа до тех пор, пока вы не получите 150 очков Q, а затем посмотрите, есть ли у вас какие-либо отличные отличия. Если это не удастся, вам придется выяснить, как идти оттуда.