Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Сортировка массива:
Сначала мы сортируем массив num. Это позволит нам использовать два указателя для нахождения наиболее близкой суммы.
Инициализация результата:
Инициализируем переменную result суммой первых трех элементов отсортированного массива. Это будет нашей начальной ближайшей суммой.
Проход по массиву:
Используем цикл for, чтобы пройти по массиву. Для каждого элемента используем два указателя j и k:
j начинается сразу после текущего элемента i.
k начинается с конца массива.
Два указателя:
Внутри цикла while, пока j меньше k, вычисляем сумму sum элементов num[i], num[j] и num[k].
Если сумма sum равна target, то возвращаем sum, так как мы нашли точное соответствие.
Обновление результата:
Если текущая сумма sum ближе к target, чем предыдущая ближайшая сумма result, обновляем result.
Сдвиг указателей:
Если sum меньше target, сдвигаем указатель j вправо, чтобы увеличить сумму.
Если sum больше target, сдвигаем указатель k влево, чтобы уменьшить сумму.
Возврат результата:
После завершения всех итераций возвращаем result, которая будет содержать сумму трех чисел, ближайшую к target.
Временная и пространственная сложность:
Временная сложность: O(n^2), где n — длина массива. Сортировка занимает O(n log n), и основной алгоритм с двумя указателями выполняется за O(n^2).
Пространственная сложность: O(1), так как мы используем только несколько дополнительных переменных, и не используем дополнительную память, зависящую от размера входных данных.
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
```class Solution:
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
return result
return result
```
Пояснение:
Сортировка массива:
Сначала мы сортируем массив num. Это позволит нам использовать два указателя для нахождения наиболее близкой суммы.
Инициализация результата:
Инициализируем переменную result суммой первых трех элементов отсортированного массива. Это будет нашей начальной ближайшей суммой.
Проход по массиву:
Используем цикл for, чтобы пройти по массиву. Для каждого элемента используем два указателя j и k:
j начинается сразу после текущего элемента i.
k начинается с конца массива.
Два указателя:
Внутри цикла while, пока j меньше k, вычисляем сумму sum элементов num[i], num[j] и num[k].
Если сумма sum равна target, то возвращаем sum, так как мы нашли точное соответствие.
Обновление результата:
Если текущая сумма sum ближе к target, чем предыдущая ближайшая сумма result, обновляем result.
Сдвиг указателей:
Если sum меньше target, сдвигаем указатель j вправо, чтобы увеличить сумму.
Если sum больше target, сдвигаем указатель k влево, чтобы уменьшить сумму.
Возврат результата:
После завершения всех итераций возвращаем result, которая будет содержать сумму трех чисел, ближайшую к target.
Временная и пространственная сложность:
Временная сложность: O(n^2), где n — длина массива. Сортировка занимает O(n log n), и основной алгоритм с двумя указателями выполняется за O(n^2).
Пространственная сложность: O(1), так как мы используем только несколько дополнительных переменных, и не используем дополнительную память, зависящую от размера входных данных.
👍12❤2🔥1