← Static tasks

16. 3Sum Closest

leetcode medium

#array#csharp#leetcode#math#medium#search#sort#two-pointers

Task

Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.

C# solution

matched/original
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        if(nums.Length < 3)
            return 0;
        Array.Sort(nums);
        int start = 0;
        int left = 1;
        int right = nums.Length - 1;
        int direction = nums[start] + nums[left] + nums[right] > 0 ? 1 : 0;
        int minDistance = int.MaxValue;
        int sum = int.MinValue;
        while (start < nums.Length - 2)
        {
            while (left < right)
            {
                int currSum = nums[start] + nums[left] + nums[right];
                if ( currSum == target )
                    return target;
                
                if (currSum < target)
                    left++;
                else 
                    right--;
                if (Math.Abs(currSum - target) < minDistance)
                {
                    sum = currSum;
                    minDistance = Math.Abs(currSum - target);
                }
            }
            start ++;
            left = start + 1;
            right = nums.Length - 1;
        }
        return sum;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ThreeSumClosest(vector<int>& nums, int target) {
        if(nums.size() < 3)
            return 0;
        sort(nums.begin(), nums.end());
        int start = 0;
        int left = 1;
        int right = nums.size() - 1;
        int direction = nums[start] + nums[left] + nums[right] > 0 ? 1 : 0;
        int minDistance = int.MaxValue;
        int sum = int.MinValue;
        while (start < nums.size() - 2)
        {
            while (left < right)
            {
                int currSum = nums[start] + nums[left] + nums[right];
                if ( currSum == target )
                    return target;
                
                if (currSum < target)
                    left++;
                else 
                    right--;
                if (abs(currSum - target) < minDistance)
                {
                    sum = currSum;
                    minDistance = abs(currSum - target);
                }
            }
            start ++;
            left = start + 1;
            right = nums.size() - 1;
        }
        return sum;
    }
}

Java solution

matched/original
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        int n = nums.length;
        int closest = 0;
        // int min = Integer.MAX_VALUE;
        int max = Integer.MAX_VALUE;
        Arrays.sort(nums);
        //target += 1;

        for(int i=0; i<n-2; i++){
            int j=i+1;
            int k  = n-1;
            // min = Math.min(min,max);

            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];

                if(sum == target)
                    return sum;

                else if(sum < target)
                    j++;

                else
                    k--;
                    int diff = Math.abs(sum - target);
                    if(diff < max){
                        max = diff;
                        closest = sum;
                    }
                }
            }   
            
        return closest;
    }
}

JavaScript solution

matched/original
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
    nums.sort((a, b) => a - b);
    let ans = 1 << 30;
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            const t = nums[i] + nums[j] + nums[k];
            if (t === target) {
                return t;
            }
            if (Math.abs(t - target) < Math.abs(ans - target)) {
                ans = t;
            }
            if (t > target) {
                --k;
            } else {
                ++j;
            }
        }
    }
    return ans;
};

Python solution

matched/original
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

Go solution

matched/original
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
}

Explanation

Проверка длины массива:

Сначала проверяется, содержит ли массив nums хотя бы три элемента. Если нет, метод возвращает 0, так как нет смысла искать сумму трёх элементов.

Сортировка массива:

Массив nums сортируется. Это необходимо для упрощения поиска комбинаций с использованием двух указателей.

Инициализация переменных:

start инициализируется на первом элементе, left на втором, и right на последнем элементе массива.

Переменные direction, minDistance, и sum инициализируются для отслеживания минимального расстояния до целевой суммы и самого близкого найденного значения суммы.

Внешний цикл:

Внешний цикл перебирает элементы массива начиная с первого. Для каждого элемента start он рассматривает комбинации элементов с использованием двух других указателей (left и right).

Внутренний цикл:

Внутренний цикл выполняется до тех пор, пока указатели left и right не пересекутся.

Рассчитывается сумма элементов, на которые указывают указатели start, left, и right.

Если сумма совпадает с целевой суммой, возвращается целевая сумма, так как это идеальный случай.

Обновление указателей и значений:

Если сумма меньше целевой, left сдвигается вправо (увеличивается), чтобы увеличить сумму.

Если сумма больше целевой, right сдвигается влево (уменьшается), чтобы уменьшить сумму.

При каждом изменении указателей обновляется минимальное расстояние между текущей суммой и целевой суммой, если новое расстояние меньше текущего.

Возвращение результата:

После завершения всех итераций возвращается значение sum, которое является суммой трех элементов, ближайшей к целевой сумме.

Временная и пространственная сложность:

Временная сложность: O(n^2), где n — количество элементов в массиве. Основная сложность обусловлена двойным перебором элементов массива (внешний цикл и внутренний цикл).

Пространственная сложность: O(1), так как используется фиксированное количество переменных для хранения данных и индексов, не зависящих от размера входных данных.