16. 3Sum Closest — LeetCode

Дан массив целых чисел nums длины n и целое число target, найдите три целых числа в nums, сумма которых ближе всего к 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).

Пример 2:

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

Ограничения:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Решения:

Питон

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()  # Sort the array
        closest_sum = float('inf')  # Initialize closest_sum to a large value
        for i in range(len(nums)):
            left = i + 1  # Left pointer
            right = len(nums) - 1  # Right pointer
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                if abs(curr_sum - target) < abs(closest_sum - target):  # Update closest_sum if necessary
                    closest_sum = curr_sum
                if curr_sum < target:  # Move left pointer
                    left += 1
                elif curr_sum > target:  # Move right pointer
                    right -= 1
                else:  # Return target if we find a combination that sums to it
                    return target
        return closest_sum

C#

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);  // Sort the array
        int closestSum = int.MaxValue;  // Initialize closestSum to a large value
        for (int i = 0; i < nums.Length; i++)
        {
            int left = i + 1;  // Left pointer
            int right = nums.Length - 1;  // Right pointer
            while (left < right)
            {
                int currSum = nums[i] + nums[left] + nums[right];
                if (Math.Abs(currSum - target) < Math.Abs(closestSum - target))  // Update closestSum if necessary
                {
                    closestSum = currSum;
                }
                if (currSum < target)  // Move left pointer
                {
                    left++;
                }
                else if (currSum > target)  // Move right pointer
                {
                    right--;
                }
                else  // Return target if we find a combination that sums to it
                {
                    return target;
                }
            }
        }
        return closestSum;
    }
}

Ява

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);  // Sort the array
        int closestSum = Integer.MAX_VALUE;  // Initialize closestSum to a large value
        for (int i = 0; i < nums.length; i++)
        {
            int left = i + 1;  // Left pointer
            int right = nums.length - 1;  // Right pointer
            while (left < right)
            {
                int currSum = nums[i] + nums[left] + nums[right];
                if (Math.abs(currSum - target) < Math.abs(closestSum - target))  // Update closestSum if necessary
                {
                    closestSum = currSum;
                }
                if (currSum < target)  // Move left pointer
                {
                    left++;
                }
                else if (currSum > target)  // Move right pointer
                {
                    right--;
                }
                else  // Return target if we find a combination that sums to it
                {
                    return target;
                }
            }
        }
        return closestSum;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);  // Sort the array
    let closestSum = Number.MAX_VALUE;  // Initialize closestSum to a large value
    for (let i = 0; i < nums.length; i++) {
        let left = i + 1;  // Left pointer
        let right = nums.length - 1;  // Right pointer
        while (left < right) {
        let currSum = nums[i] + nums[left] + nums[right];
        if (Math.abs(currSum - target) < Math.abs(closestSum - target)) {  // Update closestSum if necessary
            closestSum = currSum;
        }
        if (currSum < target) {  // Move left pointer
            left++;
        } else if (currSum > target) {  // Move right pointer
            right--;
        } else {  // Return target if we find a combination that sums to it
            return target;
        }
        }
    }
    return closestSum;
};

Типографический текст

function threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);  // Sort the array
    let closestSum = Number.MAX_VALUE;  // Initialize closestSum to a large value
    for (let i = 0; i < nums.length; i++) {
        let left = i + 1;  // Left pointer
        let right = nums.length - 1;  // Right pointer
        while (left < right) {
        let currSum = nums[i] + nums[left] + nums[right];
        if (Math.abs(currSum - target) < Math.abs(closestSum - target)) {  // Update closestSum if necessary
            closestSum = currSum;
        }
        if (currSum < target) {  // Move left pointer
            left++;
        } else if (currSum > target) {  // Move right pointer
            right--;
        } else {  // Return target if we find a combination that sums to it
            return target;
        }
        }
    }
    return closestSum;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {
        sort($nums);  // Sort the array
        $closestSum = PHP_INT_MAX;  // Initialize closestSum to a large value
        for ($i = 0; $i < count($nums); $i++) {
            $left = $i + 1;  // Left pointer
            $right = count($nums) - 1;  // Right pointer
            while ($left < $right) {
            $currSum = $nums[$i] + $nums[$left] + $nums[$right];
            if (abs($currSum - $target) < abs($closestSum - $target)) {  // Update closestSum if necessary
                $closestSum = $currSum;
            }
            if ($currSum < $target) {  // Move left pointer
                $left++;
            } else if ($currSum > $target) {  // Move right pointer
                $right--;
            } else {  // Return target if we find a combination that sums to it
                return $target;
            }
            }
        }
        return $closestSum;
    }
}

Надеюсь, это поможет! Дайте знать, если у вас появятся вопросы. Не забудьте подписаться, похлопать и оставить комментарий