Задача: №16. 3Sum Closest
Сложность: medium

Дан массив nums и целое число target.
Найти такие три числа из nums, сумма которых максимально близка к target.
Вернуть именно сумму этих трёх чисел. Гарантируется, что решение единственное.

Пример:

Input: nums = [-1,2,1,-4], target = 1  
Output: 2  
Explanation: Сумма -1 + 2 + 1 = 2 наиболее близка к 1

👨‍💻 Алгоритм:

1️⃣ Отсортировать массив nums, чтобы использовать двухуказательный подход.

2️⃣ Перебрать все возможные значения nums[i] в цикле от 0 до n - 3.
Для каждой позиции использовать два указателя j (i + 1) и k (n - 1) для поиска остальных двух чисел.

3️⃣ Для каждой тройки вычислить сумму и:
- Если она равна target — сразу вернуть.
- Иначе обновить текущий лучший ответ ans, если новая сумма ближе к target.
- Смещать указатели в зависимости от того, больше ли сумма или меньше target.

😎 Решение:

var threeSumClosest = function (nums, target) {
    nums.sort((a, b) => a - b);
    let ans = 1 << 30;
    const n = nums.length;

    for (let i = 0; i < n; ++i) {
        let j = i + 1;
        let k = n - 1;

        while (j < k) {
            const t = nums[i] + nums[j] + nums[k];

            if (t === target) {
                return t;
            }

            if (Math.abs(t - target) < Math.abs(ans - target)) {
                ans = t;
            }

            if (t > target) {
                k--;
            } else {
                j++;
            }
        }
    }

    return ans;
};

Ставь 👍 и забирай 📚 Базу знаний