Сумма триплета, ближайшая к целевой

Сумма триплета, ближайшая к целевой

Условие задачи

Даны неотсортированный массив и целевое число. Найдите триплет, сумма которого максимально близка к целевому числу, и верните эту сумму. Если одинаково близки несколько триплетов, верните меньшую сумму.

Пример 1:

1
2
3

Вход: [-2, 0, 1, 2], target=2
Выход: 1
Пояснение: сумма триплета [-2, 1, 2] ближе всего к цели.

Пример 2:

1
2
3

Вход: [-3, -1, 1, 2], target=1
Выход: 0
Пояснение: сумма триплета [-3, 1, 2] ближе всего к цели.

Пример 3:

1
2
3

Вход: [1, 0, 1, 1], target=100
Выход: 3
Пояснение: сумма триплета [1, 1, 1] ближе всего к цели.

Решение

После сортировки фиксируем первый элемент, а два других ищем указателями left и right. На каждом шаге вычисляем разницу target - currentSum и сохраняем наименьшую по модулю. При равных модулях выбираем большую разницу: она соответствует меньшей сумме триплета.

Если разница положительна, нужна большая сумма, поэтому сдвигаем left вправо. Если разница отрицательна, сдвигаем right влево. Нулевая разница означает точное совпадение с целью.

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

package main

import (
	"fmt"
	"math"
	"sort"
)

func absolute(value int) int {
	if value < 0 {
		return -value
	}
	return value
}

func searchClosestTriplet(arr []int, targetSum int) int {
	if len(arr) < 3 {
		panic("для триплета нужны как минимум три числа")
	}

	sort.Ints(arr)
	smallestDifference := math.MaxInt

	for i := 0; i < len(arr)-2; i++ {
		left, right := i+1, len(arr)-1
		for left < right {
			targetDifference := targetSum - arr[i] - arr[left] - arr[right]
			if targetDifference == 0 {
				return targetSum
			}

			if absolute(targetDifference) < absolute(smallestDifference) ||
				(absolute(targetDifference) == absolute(smallestDifference) && targetDifference > smallestDifference) {
				smallestDifference = targetDifference
			}

			if targetDifference > 0 {
				left++
			} else {
				right--
			}
		}
	}

	return targetSum - smallestDifference
}

func main() {
	fmt.Println(searchClosestTriplet([]int{-2, 0, 1, 2}, 2))
	fmt.Println(searchClosestTriplet([]int{-3, -1, 1, 2}, 1))
	fmt.Println(searchClosestTriplet([]int{1, 0, 1, 1}, 100))
}

Вывод:

1
2
3

1
0
3

Временная сложность

Сортировка занимает \(O(N \log N)\), а перебор с двумя указателями — \(O(N^2)\). Итоговая временная сложность равна \(O(N^2)\).

Пространственная сложность

Если не учитывать входной массив, сортировке может потребоваться до \(O(N)\) дополнительной памяти.