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
    28 авг 2021 в 11:35
  • Ну, стандартный способ перебора всех комбинаций, сложность О(n^3). Для каждой комбинации считаем её сумму и запоминаем сумму, если она ближе чем предыдущая сохранённая.
    – Sergey Zh.
    28 авг 2021 в 13:15
  • Sergey Zh. спасибо
    – YuriiS
    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
    28 авг 2021 в 14:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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