В этой задаче LeetCode нам дается массив чисел и предлагается найти сумму 3 ближайших чисел к заданной цели. Другими словами, учитывая массив [1, 2, 3, 4] и цель 7, мы бы вернули 7, поскольку 1 + 2 + 4 = 7. Однако если целью было 11, то самое близкое, что мы можем получить, это 2 + 3 + 4 = 9, поэтому мы бы вернули 9.
Эта задача очень похожа на задачу с тремя суммами. Однако основное отличие состоит в том, что вместо всех возможных комбинаций мы возвращаем самую близкую комбинацию (на самом деле мы возвращаем сумму ближайшей комбинации, но это не очень важно для этого сравнения).
Решение: контрактное окно
Как и в случае с задачей с тремя суммами, этот ответ включает в себя сначала перебор (упорядоченного) массива чисел. Затем для каждого числа мы устанавливаем «окно», в котором левая сторона находится на следующем числе в массиве, а правая сторона — на последнем числе.
Затем мы проверяем, нашли ли мы решение, и в этот момент мы выходим из него с его суммой. Однако, если сумма трех чисел слишком мала, мы сдвигаем левую часть окна на 1. Аналогичным образом, если сумма слишком велика, мы сдвигаем правую часть окна на 1.
В любом из приведенных выше случаев мы также записываем сумму, если она ближе к цели, чем любая предыдущая запись (поскольку мы, конечно, ищем здесь ближайшую 3-сумму).
Вот код:
