Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Задача требует нахождения суммы трёх чисел в массиве nums, которая наиболее близка к заданному значению target. Рассмотрим алгоритм подробнее.
Алгоритм:
Инициализация:
Переменная closest для хранения суммы трёх чисел, наиболее близкой к target.
Переменная max для хранения минимальной разницы между текущей суммой и target.
Сортировка массива:
Сначала сортируем массив nums для упрощения поиска трёх чисел.
Поиск тройки:
Используем цикл, чтобы пройти по массиву nums до третьего с конца элемента.
Для каждого элемента устанавливаем два указателя: j (следующий элемент) и k (последний элемент).
Вычисление суммы:
Внутри вложенного цикла вычисляем сумму текущих трёх чисел sum = nums[i] + nums[j] + nums[k].
Если сумма равна target, возвращаем sum как ответ.
Если сумма меньше target, увеличиваем j, чтобы увеличить сумму.
Если сумма больше target, уменьшаем k, чтобы уменьшить сумму.
Обновление ближайшей суммы:
Вычисляем разницу diff между текущей суммой и target.
Если эта разница меньше max, обновляем max и closest.
Возврат результата:
После завершения всех итераций возвращаем closest как сумму, наиболее близкую к target. Временная и пространственная сложность:
Временная сложность: O(n^2), где n - длина массива nums. Это связано с вложенным циклом и операцией сортировки (которая выполняется за O(n log n)).
Пространственная сложность: O(1), так как используется постоянное количество дополнительной памяти.
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
int closest = 0;
// int min = Integer.MAX_VALUE;
int max = Integer.MAX_VALUE;
Arrays.sort(nums);
//target += 1;
for(int i=0; i<n-2; i++){
int j=i+1;
int k = n-1;
// min = Math.min(min,max);
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;
}
}Пояснение:
Задача требует нахождения суммы трёх чисел в массиве nums, которая наиболее близка к заданному значению target. Рассмотрим алгоритм подробнее.
Алгоритм:
Инициализация:
Переменная closest для хранения суммы трёх чисел, наиболее близкой к target.
Переменная max для хранения минимальной разницы между текущей суммой и target.
Сортировка массива:
Сначала сортируем массив nums для упрощения поиска трёх чисел.
Поиск тройки:
Используем цикл, чтобы пройти по массиву nums до третьего с конца элемента.
Для каждого элемента устанавливаем два указателя: j (следующий элемент) и k (последний элемент).
Вычисление суммы:
Внутри вложенного цикла вычисляем сумму текущих трёх чисел sum = nums[i] + nums[j] + nums[k].
Если сумма равна target, возвращаем sum как ответ.
Если сумма меньше target, увеличиваем j, чтобы увеличить сумму.
Если сумма больше target, уменьшаем k, чтобы уменьшить сумму.
Обновление ближайшей суммы:
Вычисляем разницу diff между текущей суммой и target.
Если эта разница меньше max, обновляем max и closest.
Возврат результата:
После завершения всех итераций возвращаем closest как сумму, наиболее близкую к target. Временная и пространственная сложность:
Временная сложность: O(n^2), где n - длина массива nums. Это связано с вложенным циклом и операцией сортировки (которая выполняется за O(n log n)).
Пространственная сложность: O(1), так как используется постоянное количество дополнительной памяти.
👍9