Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Сортировка массива:
Сначала функция сортирует массив nums. Сортировка упрощает задачу поиска трех чисел, сумма которых близка к заданному значению, поскольку позволяет эффективно использовать двухсвязный указатель для поиска.
Инициализация переменных:
ans используется для хранения ответа — суммы трех чисел, наиболее близкой к target.
diff хранит минимальное различие между суммой трех чисел и target. Изначально оно установлено в math.MaxInt для обеспечения того, что любая первая сумма будет меньше этого значения.
Основной цикл:
Внешний цикл итерирует по элементам массива nums, рассматривая каждый элемент как первую вершину трех чисел.
Внутренний цикл использует двухсвязный указатель (low и high) для перебора оставшихся двух элементов массива, начиная с элементов, находящихся сразу после текущего элемента внешнего цикла и до конца массива.
Проверка сумм и обновление ответа:
Для каждого сочетания трех чисел (nums[i], nums[low], nums[high]) проверяется их сумма:
Если сумма равна target, возвращается target сразу, так как это идеальное совпадение.
В противном случае, если текущая сумма ближе к target, чем предыдущие, обновляется переменная diff и ans.
Если сумма больше target, указатель high сдвигается влево, чтобы уменьшить сумму.
Если сумма меньше target, указатель low сдвигается вправо, чтобы увеличить сумму.
Возврат результата:
После завершения всех итераций возвращается значение ans, которое представляет собой сумму трех чисел, наиболее близкую к target.
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
var ans int
diff:=math.MaxInt
for i:=0;i<len(nums)-2;i++{
low:=i+1
high:=len(nums)-1
for low<high{
if nums[i]+nums[low]+nums[high]==target{
ans=target
return ans
}else if int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))<diff{
diff=int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))
ans=nums[i]+nums[low]+nums[high]
}
if nums[i]+nums[low]+nums[high]>target{
high--
}else{
low++
}
}
}
return ans
}Пояснение:
Сортировка массива:
Сначала функция сортирует массив nums. Сортировка упрощает задачу поиска трех чисел, сумма которых близка к заданному значению, поскольку позволяет эффективно использовать двухсвязный указатель для поиска.
Инициализация переменных:
ans используется для хранения ответа — суммы трех чисел, наиболее близкой к target.
diff хранит минимальное различие между суммой трех чисел и target. Изначально оно установлено в math.MaxInt для обеспечения того, что любая первая сумма будет меньше этого значения.
Основной цикл:
Внешний цикл итерирует по элементам массива nums, рассматривая каждый элемент как первую вершину трех чисел.
Внутренний цикл использует двухсвязный указатель (low и high) для перебора оставшихся двух элементов массива, начиная с элементов, находящихся сразу после текущего элемента внешнего цикла и до конца массива.
Проверка сумм и обновление ответа:
Для каждого сочетания трех чисел (nums[i], nums[low], nums[high]) проверяется их сумма:
Если сумма равна target, возвращается target сразу, так как это идеальное совпадение.
В противном случае, если текущая сумма ближе к target, чем предыдущие, обновляется переменная diff и ans.
Если сумма больше target, указатель high сдвигается влево, чтобы уменьшить сумму.
Если сумма меньше target, указатель low сдвигается вправо, чтобы увеличить сумму.
Возврат результата:
После завершения всех итераций возвращается значение ans, которое представляет собой сумму трех чисел, наиболее близкую к target.
🤔3👍1