0

Дается массив из n чисел (числа могут быть как положительные, так и отрицательные) и число t. Необходимо найти сумму sum из трех элементов массива ближайшую к t. К примеру n = [-1, 2, 1, -4]; t = 1; sum = -1 + 2 + 1 = 2;

Не соображу как идти циклом по массиву, чтобы получить сумму из трех элементов всех возможных вариантов. Помогите разобраться

2 ответа 2

1

Три вложенных цикла i = 0..n-1, j = 0..n-1, k = 0..n-1

Считаем sum для элементов массива с индексами i, j, k если индексы не равны между собой (i!=j, j!=k, i!=k)

Запоминаем sum, если она меньше сохранённый суммы.

3
  • Sergey Zh. а можно подробней пояснить ?
    – YuriiS
    Commented 28 авг. 2021 в 11:35
  • Ну, стандартный способ перебора всех комбинаций, сложность О(n^3). Для каждой комбинации считаем её сумму и запоминаем сумму, если она ближе чем предыдущая сохранённая.
    – Sergey Zh.
    Commented 28 авг. 2021 в 13:15
  • Sergey Zh. спасибо
    – YuriiS
    Commented 28 авг. 2021 в 14:23
0
int[] array = <массив из n чисел>;
int t = <нужное значение>;
int closerSum = 0;
int tempDifference = Integer.MAX_VALUE;
for (int indexOfNumberOne = 0; indexOfNumberOne < array.length; indexOfNumberOne++) {
    for (int indexOfNumberTwo = indexOfNumberOne + 1; indexOfNumberTwo < array.length; indexOfNumberTwo++) {
        for (int indexOfNumberThree = indexOfNumberTwo + 1; indexOfNumberThree < array.length; indexOfNumberThree++) {
            int sum = array[indexOfNumberOne] +  array[indexOfNumberTwo] + array[indexOfNumberThree];
            if (sum == t) {
                return sum; // здесь заканчиваем, т.к. ближе равенства ничего быть не может.
            }
            if (Math.abs(t - sum) < tempDifference) {
                tempDifference = Math.abs(t - sum);
                closerSum = sum;
            }
        }
    }
}

Что-то типа такого. Как и написал выше Сергей, только не просто минимальное, а наиболее близкое. Нам надо сравнить все возможные уникальные суммы трех чисел в массиве. Могут быть ошибки, писал сразу в броузере.

1
  • Pentiux, спасибо, буду разбираться
    – YuriiS
    Commented 28 авг. 2021 в 14:23

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.