Дан массив целых чисел nums и целое число target. Нужно найти такую тройку чисел в массиве с различными индексами, что их сумма наиболее близка к target.
Вывести необходимо сумму трех чисел.
Пример
Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2 (-1 + 2 + 1 = 2)
Input: nums = [0,0,0], target = 1
Output: 0
Решение:
Пусть нужно найти тройку i, j, k (i != j != k), у которой nums[i] + nums[j] + nums[k] == target
Отсортируем массив, будем поддерживать наилучшую сумму и минимальную разницу между этой суммой и target
Переберем циклом указатель i, инициализируем j = i + 1, k = n - 1 и пока j < k каждый раз будем проверять:
- если текущая сумма равна target, то выводим ответ и заканчиваем
- если сумма меньше target, то двигаем j вправо
- иначе двигаем k влево
Сохраняем минимальную разницу, если она меньше, чем была, то сохраняем сумму
Асимптотика O(n^2)
@algoses