HomeLeetcode16. 3Sum Closest - Leetcode Solutions
Leetcode

16. 3Sum Closest – Leetcode Solutions

Declan Clarke

Description:

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 input would have exactly one solution.

Examples:

Example 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).

Example 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).

Solution in Python:

To solve the problem of finding three integers in an array such that their sum is closest to a given target, we can use a two-pointer approach after sorting the array. This approach ensures that we efficiently find the closest sum without needing to check all possible combinations explicitly.

Python
from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # First, sort the array
        nums.sort()
        # Initialize the closest sum to the sum of the first three elements
        closest_sum = nums[0] + nums[1] + nums[2]
        
        # Iterate through the array, considering each element as a potential first element of the triplet
        for i in range(len(nums) - 2):
            # Use two pointers to find the best pair for the current element
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                # If the current sum is exactly the target, we can return immediately
                if current_sum == target:
                    return current_sum
                
                # Update the closest sum if the current sum is closer to the target
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                
                # Move the pointers based on the comparison between current_sum and target
                if current_sum < target:
                    left += 1
                else:
                    right -= 1
        
        return closest_sum

Detailed Comments on the Code:

  1. Sorting the Array:
    • The first step is to sort the input array. Sorting helps us to use the two-pointer technique effectively.
  2. Initialization:
    • We initialize closest_sum to a very large value (float('inf')). This will store the closest sum we have found so far.
  3. Main Loop:
    • We iterate through the array with index i from 0 to len(nums) - 2. This loop considers each element as the potential first element of the triplet.
    • For each i, we use two pointers left and right to find the other two elements of the triplet:
      • left starts just after i (i + 1).
      • right starts at the end of the array.
  4. Two-Pointer Technique:
    • Inside the main loop, we enter a while loop where left < right.
    • Calculate the current_sum of the triplet (nums[i] + nums[left] + nums[right]).
    • If current_sum exactly matches the target, we immediately return current_sum.
    • If current_sum is closer to the target than the previous closest sum, we update closest_sum.
    • Depending on whether current_sum is less than or greater than the target, we move the left or right pointer respectively to try to get closer to the target.
  5. Return the Closest Sum:
    • After the loops finish, we return closest_sum, which holds the sum of the triplet closest to the target.

Solution in Javascript:

JavaScript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    // First, sort the array to use the two-pointer technique
    nums.sort((a, b) => a - b);
    
    // Initialize the closest sum to the sum of the first three elements
    let closestSum = nums[0] + nums[1] + nums[2];
    
    // Iterate through the array, considering each element as a potential first element of the triplet
    for (let i = 0; i < nums.length - 2; i++) {
        // Use two pointers to find the best pair for the current element
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            let currentSum = nums[i] + nums[left] + nums[right];
            
            // If the current sum is exactly the target, we can return immediately
            if (currentSum === target) {
                return currentSum;
            }
            
            // Update the closest sum if the current sum is closer to the target
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }
            
            // Move the pointers based on the comparison between currentSum and target
            if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return closestSum;
};

Solution in Java:

Java
import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // First, sort the array to use the two-pointer technique
        Arrays.sort(nums);
        
        // Initialize the closest sum to the sum of the first three elements
        int closestSum = nums[0] + nums[1] + nums[2];
        
        // Iterate through the array, considering each element as a potential first element of the triplet
        for (int i = 0; i < nums.length - 2; i++) {
            // Use two pointers to find the best pair for the current element
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                // If the current sum is exactly the target, we can return immediately
                if (currentSum == target) {
                    return currentSum;
                }
                
                // Update the closest sum if the current sum is closer to the target
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                
                // Move the pointers based on the comparison between currentSum and target
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closestSum;
    }
}

Solution in C#:

C#
using System;

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        // First, sort the array to use the two-pointer technique
        Array.Sort(nums);
        
        // Initialize the closest sum to the sum of the first three elements
        int closestSum = nums[0] + nums[1] + nums[2];
        
        // Iterate through the array, considering each element as a potential first element of the triplet
        for (int i = 0; i < nums.Length - 2; i++) {
            // Use two pointers to find the best pair for the current element
            int left = i + 1;
            int right = nums.Length - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                // If the current sum is exactly the target, we can return immediately
                if (currentSum == target) {
                    return currentSum;
                }
                
                // Update the closest sum if the current sum is closer to the target
                if (Math.Abs(currentSum - target) < Math.Abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                
                // Move the pointers based on the comparison between currentSum and target
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closestSum;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com