Задача "16. 3Sum Closest"

Решила попробовать добавлять ссылку в заголовок, потестим удобство.

Итак, тут не было постов аж 2 недели, пора возвращаться в ритм.

Сегодня разобрала две medium задачи, в обеих из которых использовался метод двух указателей. Поделюсь той, что поинтереснее🙌

Уровень: medium

Условие следующее: дан массив чисел, размер массива n и целевое значение target. Требуется найти 3 таких числа в массиве, сумма которых ближе всего к целевому значению, и вернуть их сумму.
p.s. каждый входной набор данных имеет только одно решение

Итак, погнали алгоритм:
1. Сортируем массив
2. Берем какое-то базовое значение, чтобы было от чего оттолкнуться, пусть это будет сумма первых трех чисел.
3. Проходимся по каждому числу массива, сужая потенциально возможные суммы за счет метода двух указателей, и сравнивая с целевым значением.

Третий пункт сложноват для восприятия в одном предложении, согласна. Посмотрим на примере:
[-1,2,1,-4, 12, 5, 9, -3] - наш массив, 7 - target (целевое значение)

1. Сортируем [-4, -3, -1, 1, 2, 5, 9, 12]
2. Берем за базу сумму первых трех чисел: (-4) + (-3) + (-1) = -8
3. Заходим в цикл по нашему массиву, начиная с первого значения (-4), т.е. i = 0, присваивая значения указателей left = i + 1; right = nums.length - 1.
Для первого круга: left = 1; right = 7.
- Находим текущую сумму: -4 + (-3) + 12 = 5
- Если она равна целевому значению, ура, возвращаем ее, конец.
Иначе:
- Сравниваем по модулю разницы между таргетом и базовой суммой и между таргетом и текущей суммой. Если первый модуль больше, то заменяем базовую сумму на текущую: 7 - (-8) = 15, 7 - 5 =2. |15| > |2| => базовая сумма = 5.
- Двигаем границы: если базовая сумма меньше таргета => двигаем левый указатель, иначе правый. В нашем случае двигаем левый, теперь left = -1.
- Заново рассчитываем текущую сумму: -4 + (-1) + 12 = 7 - ура, это и был наш таргет, возвращаем.

Теперь код:

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int threeSumClosest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1; 
        int right = nums.length - 1;

        while (left < right) {
            int currentThreeSum = nums[i] + nums[left] + nums[right];
            if (currentThreeSum == target) {
                return currentThreeSum;
            }
            if (Math.abs(target - currentThreeSum) < Math.abs (target - threeSumClosest)) {
                threeSumClosest = currentThreeSum;
            }
            if (currentThreeSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return threeSumClosest;
}

Временная сложность: O(n^2), к сожалению лучше нельзя, т.к. нужно рассмотреть комбинации для трех чисел, а поэтому в худшем случае нам придется пройти по всем числам массива внешним циклом, что займет O(n), а внутренним двигать указатели, что также O(n). Ну, еще и сортировка O(n * log n), но общая все равно O(n^2), т.к. она доминирует

Пространственная сложность: O(1), т.к. тут только константы используем под память.