Golang Юниор

Наиближайшая сумма трёх

Сложность: Средняя

Условие задачи: Дан целочисленный массив и целевое значение суммы. Нужно найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.

Каждый массив имеет единственное решение.

Пример:

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2
Объяснение: (-1 + 2 + 1 = 2)

Ввод: nums = [0,0,0], target = 1
Вывод: 0

Решение:

func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
ans := 0
dist := int(^uint(0) >> 1) //dist = infinity

for i :=0; i<len(nums); i++{
l := i+1
r := len(nums)-1

for l < r{
sum := nums[i] + nums[l] + nums[r]
if sum == target{
return sum
}
if sum < target{
l = l + 1
if target - sum < dist{
dist = target-sum
ans = sum
}
}else{
r = r - 1
if sum - target < dist{
dist = sum-target
ans = sum
}
}
}
}
return ans
}

Временная сложность: O(nlogn)

Пространственная сложность: O(1)

Пишите свое решение в комментариях👇

LeetCode

3Sum Closest - LeetCode

Can you solve this real interview question? 3Sum Closest - Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each…

www.tgoop.com/golangprofi/501

3.1K viewsJun 3, 2024 at 18:38

Наиближайшая сумма трёх

Сложность: Средняя

Условие задачи: Дан целочисленный массив и целевое значение суммы. Нужно найти три числа из массива, которые либо в результате суммирования равны значению целевой суммы либо же максимально близки к ней по модулю.

Каждый массив имеет единственное решение.

Пример:

Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2
Объяснение: (-1 + 2 + 1 = 2)

Ввод: nums = [0,0,0], target = 1
Вывод: 0

Решение:

func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
ans := 0
dist := int(^uint(0) >> 1) //dist = infinity

for i :=0; i<len(nums); i++{
l := i+1
r := len(nums)-1

for l < r{
sum := nums[i] + nums[l] + nums[r]
if sum == target{
return sum
}
if sum < target{
l = l + 1
if target - sum < dist{
dist = target-sum
ans = sum
}
}else{
r = r - 1
if sum - target < dist{
dist = sum-target
ans = sum
}
}
}
}
return ans
}

Временная сложность: O(nlogn)

Пространственная сложность: O(1)

Пишите свое решение в комментариях👇

BY Golang Юниор