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

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"

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

1⃣Отсортировать массив nums.

2⃣Для каждого элемента использовать два указателя: один в начале оставшегося массива, другой — в конце.

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

😎 Решение:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int closest = 0;
        int max = Integer.MAX_VALUE;
        Arrays.sort(nums);

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

            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                if(sum == target)
                    return sum;
                else if(sum < target)
                    j++;
                else
                    k--;

                int diff = Math.abs(sum - target);
                if(diff < max) {
                    max = diff;
                    closest = sum;
                }
            }
        }
        return closest;
    }
}

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