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

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

Пример:

Input: nums = [-1,2,1,-4], target = 1
Output: 2

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

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

2⃣Для каждого числа nums[i], зафиксировать его и искать пару чисел в подмассиве справа с помощью двух указателей (front, back), чтобы сумма тройки была ближе всего к target.

3⃣Обновлять текущую лучшую сумму, если новая тройка ближе к target, чем предыдущая. Вернуть финальный результат.

😎 Решение:

class Solution { 
public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        sort(nums.begin(), nums.end()); 
        int sum = nums[0] + nums[1] + nums[2]; 
        int sum1 = 0; 
        
        for (int i = 0; i < nums.size(); i++) { 
            int front = i + 1; 
            int back = nums.size() - 1; 
            
            while (front < back) { 
                sum1 = nums[i] + nums[front] + nums[back]; 
                
                if (abs(sum1 - target) <= abs(sum - target)) { 
                    sum = sum1; 
                } 
                
                if (sum1 > target)  
                    back--; 
                else if (sum1 < target)  
                    front++; 
                else 
                    return sum1; 
            } 
        } 
        return sum; 
    } 
};

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