🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: №16. 3Sum Closest
Сложность: medium
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Пример:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
👨💻 Алгоритм:
1⃣Отсортировать массив и инициализировать переменные для отслеживания минимальной разницы.
2⃣Использовать два указателя (left и right) для поиска суммы трех чисел, обновляя их в зависимости от текущей суммы.
3⃣Возвращать сумму, которая наиболее близка к target.
😎 Решение:
public class Solution {
public int ThreeSumClosest(int[] nums, int target) {
Array.Sort(nums);
int closestSum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.Length - 2; i++) {
int left = i + 1, right = nums.Length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum)) {
closestSum = currentSum;
}
if (currentSum < target) {
left++;
} else {
right--;
}
}
}
return closestSum;
}
}
Ставь 👍 и забирай 📚 Базу знаний