3Sum Closest

                                            
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int closestSum = INT_MAX;
        int minDiff = INT_MAX;
        
        for (int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
                
                int currentDiff = abs(sum - target);
                if (currentDiff < minDiff) {
                    minDiff = currentDiff;
                    closestSum = sum;
                }
            }
        }
        
        return closestSum;
    }
};

                                            
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closestSum = Integer.MAX_VALUE;
        int minDiff = Integer.MAX_VALUE;
        
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == target) {
                    return sum;
                }
                
                if (Math.abs(sum - target) < minDiff) {
                    minDiff = Math.abs(sum - target);
                    closestSum = sum;
                }
                
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return closestSum;
    }
}

                                            
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        closest_sum = float('inf')
        
        for i in range(len(nums)-2):
            left, right = i+1, len(nums)-1
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if abs(target - current_sum) < abs(target - closest_sum):
                    closest_sum = current_sum
                
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return target
        
        return closest_sum

                                            
int threeSumClosest(int* nums, int numsSize, int target) {
    int closestSum = nums[0] + nums[1] + nums[2];
    int diff = abs(closestSum - target);
    
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                int sum = nums[i] + nums[j] + nums[k];
                int newDiff = abs(sum - target);
                
                if (newDiff < diff) {
                    closestSum = sum;
                    diff = newDiff;
                }
            }
        }
    }
    
    return closestSum;
}

                                            
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = nums[0] + nums[1] + nums[2];
    
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            
            if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                closestSum = currentSum;
            }
            
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    
    return closestSum;
};

                                            
function threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);
    let closestSum = nums[0] + nums[1] + nums[2];
    
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }
            
            if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return closestSum;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {
        sort($nums);
        $closestSum = $nums[0] + $nums[1] + $nums[2];

        for ($i = 0; $i < count($nums) - 2; $i++) {
            $left = $i + 1;
            $right = count($nums) - 1;

            while ($left < $right) {
                $currentSum = $nums[$i] + $nums[$left] + $nums[$right];

                if (abs($target - $currentSum) < abs($target - $closestSum)) {
                    $closestSum = $currentSum;
                }

                if ($currentSum < $target) {
                    $left++;
                } else {
                    $right--;
                }
            }
        }

        return $closestSum;
    }
}

                                            
class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        let nums = nums.sorted()
        var closestSum = nums[0] + nums[1] + nums[2]

        for i in 0..<nums.count {
            var left = i + 1
            var right = nums.count - 1
            while left < right {
                let currentSum = nums[i] + nums[left] + nums[right]
                if abs(currentSum - target) < abs(closestSum - target) {
                    closestSum = currentSum
                }

                if currentSum < target {
                    left += 1
                } else if currentSum > target {
                    right -= 1
                } else {
                    return target
                }
            }
        }

        return closestSum
    }
}

                                            
class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        nums.sort()
        var closestSum = nums[0] + nums[1] + nums[2]

        for (i in nums.indices) {
            var left = i + 1
            var right = nums.size - 1

            while (left < right) {
                val currentSum = nums[i] + nums[left] + nums[right]

                if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                    closestSum = currentSum
                }

                if (currentSum < target) {
                    left++
                } else {
                    right--
                }
            }
        }

        return closestSum
    }
}

                                            
class Solution {
  int threeSumClosest(List<int> nums, int target) {
    nums.sort();
    int closestSum = nums[0] + nums[1] + nums[2];

    for (int i = 0; i < nums.length - 2; i++) {
      int left = i + 1;
      int right = nums.length - 1;

      while (left < right) {
        int currentSum = nums[i] + nums[left] + nums[right];

        if ((currentSum - target).abs() < (closestSum - target).abs()) {
          closestSum = currentSum;
        }

        if (currentSum < target) {
          left++;
        } else {
          right--;
        }
      }
    }

    return closestSum;
  }
}

                                            
func threeSumClosest(nums []int, target int) int {
    closestSum := nums[0] + nums[1] + nums[2]
    minDiff := abs(closestSum - target)

    sort.Ints(nums)

    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            currentSum := nums[i] + nums[left] + nums[right]
            if currentDiff := abs(currentSum - target); currentDiff < minDiff {
                minDiff = currentDiff
                closestSum = currentSum
            }
            if currentSum < target {
                left++
            } else {
                right--
            }
        }
    }

    return closestSum
}

func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

                                            
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def three_sum_closest(nums, target)
    nums.sort!
    closest_sum = nums[0] + nums[1] + nums[2]
    
    (0...nums.length-2).each do |i|
        left = i + 1
        right = nums.length - 1
        
        while left < right
            current_sum = nums[i] + nums[left] + nums[right]
            if (current_sum - target).abs < (closest_sum - target).abs
                closest_sum = current_sum
            end
            
            if current_sum < target
                left += 1
            else
                right -= 1
            end
        end
    end
    
    return closest_sum
end

                                            
object Solution {
    import scala.util.control.Breaks._

    def threeSumClosest(nums: Array[Int], target: Int): Int = {
        val sortedNums = nums.sorted
        var closestSum = sortedNums(0) + sortedNums(1) + sortedNums(2)
        var result = 0

        for (i <- 0 until sortedNums.length - 2) {
            var left = i + 1
            var right = sortedNums.length - 1

            breakable {
                while (left < right) {
                    val currentSum = sortedNums(i) + sortedNums(left) + sortedNums(right)

                    if (math.abs(target - currentSum) < math.abs(target - closestSum)) {
                        closestSum = currentSum
                    }

                    if (currentSum < target) {
                        left += 1
                    } else if (currentSum > target) {
                        right -= 1
                    } else {
                        result = currentSum
                        break
                    }
                }
            }
        }

        if (result != 0) result else closestSum
    }
}

                                            
impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut closest_sum = nums[0] + nums[1] + nums[2];
        
        for i in 0..nums.len() {
            let (mut left, mut right) = (i + 1, nums.len() - 1);
            while left < right {
                let sum = nums[i] + nums[left] + nums[right];
                if (sum - target).abs() < (closest_sum - target).abs() {
                    closest_sum = sum;
                }
                if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
        
        closest_sum
    }
}

To solve this coding challenge, we need to implement an algorithm that identifies three integers from the given list such that their sum is the closest to the specified target. This algorithm must then return that sum. Here's a detailed explanation on how we can approach and solve this.

Explanation

Understanding the Problem:

Input : An array of integers
nums

and an integer
target

.
Output : The sum of three integers from the array
nums

that is closest to the
target

.

Example:

Given

nums = [-1, 2, 1, -4]

and

target = 1

The possible sums of triplets are:

(-1 + 2 + 1) = 2
(-1 + 2 - 4) = -3
(-1 + 1 - 4) = -4
(2 + 1 - 4) = -1

The sum that is closest to 1 is 2.

Constraints:

The array
nums

has at least 3 elements, and can have up to 500 elements.
Element values are within -1000 to 1000.
The
target

value is within -10,000 to 10,000.

Detailed Steps in Pseudocode:

Sort the array to allow for the two-pointer approach.
Initialize a variable
closest_sum

to store the sum closest to the target. We'll start with a large value, such as infinity.
Iterate through the array with index
i

from 0 to
len(nums) - 3

, because we need at least two more elements to form a triplet.

For each element at index
i

, use a two-pointer technique to find the remaining two numbers.
The
left

pointer is initialized to
i + 1

, representing the start of the subarray to the right of
i

.
The
right

pointer is initialized to
len(nums) - 1

, representing the end of the array.

Two-pointer Logic :

Calculate the sum of the triplet:
nums[i] + nums[left] + nums[right]

.
If this sum is closer to the
target

than
closest_sum

, update
closest_sum

.
Adjust the pointers:

If the sum is less than the target, increment the
left

pointer to increase the sum.
If the sum is greater than the target, decrement the
right

pointer to decrease the sum.
If the sum equals the target, return the target immediately as it's the best possible result.

After exiting the loop, return
closest_sum

.

Pseudocode

                                            
# Sort the array to use two-pointer approach
sort(nums)

# Initialize closest_sum with an infinitely large value
closest_sum = Infinity

# Iterate through the array
for i from 0 to length(nums) - 3:
    left = i + 1
    right = length(nums) - 1
    
    # While the two pointers don't overlap
    while left < right:
        # Calculate the current sum of the triplet
        current_sum = nums[i] + nums[left] + nums[right]
        
        # If current_sum is closer to target than closest_sum, update closest_sum
        if abs(target - current_sum) < abs(target - closest_sum):
            closest_sum = current_sum
            
        # Adjust the pointers
        if current_sum < target:
            left += 1  # Need a larger sum, move left pointer to the right
        elif current_sum > target:
            right -= 1  # Need a smaller sum, move right pointer to the left
        else:
            # Exact match found, return the target
            return target

# Return the closest sum found
return closest_sum

By following these detailed steps and understanding the logic behind sorting the array and using the two-pointer technique, we can efficiently solve this problem within the given constraints.