Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
1. Сначала мы сортируем массив $nums в порядке возрастания.2. Затем мы используем две указателя - $key_left и $key_right, которые указывают на начало и конец массива соответственно.
3. Для каждой пары чисел $nums[$key_left] и $nums[$key_right] мы ищем третье число, которое делает сумму этих трех чисел максимально близкой к $target. Для этого мы используем двоичный поиск в оставшейся части массива.4. Во время двоичного поиска мы отслеживаем наиболее близкое к $target значение суммы трех чисел и обновляем $res соответственно.
5. После того, как мы нашли наиболее близкую сумму, мы двигаем указатели $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Ключевые моменты:
1. Использование функции $fIsCloserS для определения, какая сумма ближе к $target.2. Применение двоичного поиска для поиска третьего числа, которое делает сумму наиболее близкой к $target.
3. Обновление $res (наиболее близкой суммы) после каждой итерации.4. Перемещение указателей $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Общая временная сложность этого решения - O(n^2 * log n), где n - длина массива $nums. Это связано с сортировкой массива (O(n * log n)) и двумя вложенными циклами, каждый из которых выполняет двоичный поиск (O(log n)).
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
class Solution {
function threeSumClosest($nums, $target) {
$fIsCloserS = function ($base, $f, $s) {
return abs($base - $f) < abs($base - $s);
};
sort($nums);
$res = $middle = INF;
$key_left = 0;
$key_right = array_key_last($nums);
while ($key_left + 1 < $key_right) {
$needle = $target - $nums[$key_right] - $nums[$key_left];
$bin_key_left = $key_left + 1;
$bin_key_right = $key_right - 1;
while ($bin_key_left <= $bin_key_right) {
$bin_key_middle = (int)round(($bin_key_left + $bin_key_right) / 2);
if ($fIsCloserS($needle, $nums[$bin_key_middle], $middle)) {
$middle = $nums[$bin_key_middle];
}
if (($needle - $nums[$bin_key_middle]) < 0) {
$bin_key_right = $bin_key_middle - 1;
}
else $bin_key_left = $bin_key_middle + 1;
}
$sum = $nums[$key_right] + $nums[$key_left] + $middle;
if ($fIsCloserS($target, $sum, $res)) {
if ($sum === $target) {
return $sum;
}
$res = $sum;
}
$new_left = $nums[$key_left + 1];
$new_right = $nums[$key_right - 1];
if ($fIsCloserS($needle, $new_left, $new_right)
|| ($new_left === $new_right && $new_left === $nums[$key_left])
) $key_right--;
else $key_left++;
}
return $res;
}
} Пояснение:
1. Сначала мы сортируем массив $nums в порядке возрастания.2. Затем мы используем две указателя - $key_left и $key_right, которые указывают на начало и конец массива соответственно.
3. Для каждой пары чисел $nums[$key_left] и $nums[$key_right] мы ищем третье число, которое делает сумму этих трех чисел максимально близкой к $target. Для этого мы используем двоичный поиск в оставшейся части массива.4. Во время двоичного поиска мы отслеживаем наиболее близкое к $target значение суммы трех чисел и обновляем $res соответственно.
5. После того, как мы нашли наиболее близкую сумму, мы двигаем указатели $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Ключевые моменты:
1. Использование функции $fIsCloserS для определения, какая сумма ближе к $target.2. Применение двоичного поиска для поиска третьего числа, которое делает сумму наиболее близкой к $target.
3. Обновление $res (наиболее близкой суммы) после каждой итерации.4. Перемещение указателей $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Общая временная сложность этого решения - O(n^2 * log n), где n - длина массива $nums. Это связано с сортировкой массива (O(n * log n)) и двумя вложенными циклами, каждый из которых выполняет двоичный поиск (O(log n)).
👍2👀1💊1