16. 3Sum Closest

https://leetcode.com/problems/3sum-closest/

C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int result = INT_MAX / 2;
        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 target;
                }
                if (abs(sum - target) < abs(result - target)) {
                    result = sum;
                }
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};

Go

func threeSumClosest(nums []int, target int) int {
  sort.Ints(nums)
  result := math.MaxInt / 2
  for i := 0; i < len(nums)-2; i++ {
    left, right := i+1, len(nums)-1
    for left < right {
      sum := nums[i] + nums[left] + nums[right]
      if sum == target {
        return target
      }
      if math.Abs(float64(sum-target)) < math.Abs(float64(result-target)) {
        result = sum
      }
      if sum < target {
        left++
      } else {
        right--
      }
    }
  }
  return result
}

JavaScript

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

Python

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