16. 3Sum Closest

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2020-06-01 152 слов Одна минута

Содержание

Условие задачи

Дан массив целых чисел nums и целое число target. Необходимо найти сумму трех элементов исходного массива, которая наиболее близка к target и вернуть эту суммуу.

пример 1

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Ограничения

3 <= len(nums) <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

Решение

Brute force

func threeSumClosest(nums []int, target int) int {
    a:= make(map[int]int,0)
    
    for idx:=range nums {
        a[nums[idx]]++
    }
    
    closest := math.MaxInt32
    ressum := target

    for idx := range a {
        a[idx]--
        for jdx:= range a {
            if a[jdx] <= 0 {
                continue
            }
            a[jdx]--
            
            for kdx := range a {
                if a[kdx] <= 0 {
                    continue
                }
                
                sum := idx+jdx+kdx
                if int(math.Abs(float64(target-sum))) < closest {
                    ressum = sum
                    closest = int(math.Abs(float64(target-sum)))
                }
            }
                        
            a[jdx]++
        }
        a[idx]++
    }
    
    return ressum
}