LeetCode: 3Sum Closest

Solution for LeetCode 3sum Closet, with Cpp/Java/Python

LeetCode Problem

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

Given an array nums of n integers 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.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Explaination

Naive solution will enumerate the array with three loop:

diff = max_integer
for(a = 0, a < arr.size(), a++) 
 for(b = a+1, b < arr.size() - 1, b++) 
   for(c = b+1, c < arr.size() - 1, c++) 
     if(abs(target - (a+b+c) < diff) 
        update diff ...

The time complexity of course should be $O(N^3)$.

Actually this problem is almost same with previous LeetCode: 3Sum, except we need to find the closet sum of three elements.

Sort the array and use the method of fixing head or tail index, according to current sum, the complexity will be $O(N^2)$.

C++

class Solution {
public:
  int threeSumClosest(vector<int> &num, int target) {
    int diff = INT_MAX;
    int ans = 0;
    sort(num.begin(), num.end());

    if(num.size() < 3) return ans;
    for(size_t first = 0; first < num.size(); first++) {
      int head = first + 1;
      int tail = num.size() - 1;
      while(head < tail) {
        int sum3 = num[head] + num[tail] + num[first];
        int d = abs(sum3 - target);
        if(d == 0) return target;
        if(d < diff) {
          diff = d;
          ans = sum3;
        }
        if(sum3 > target) tail--;
        if(sum3 < target) head++;
      }
      // skip the same elements
      while(first < num.size()-1 && num[first+1] == num[first])
        first++;
    }
    return ans;
  }
};

Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int diff =  Integer.MAX_VALUE;
        int ans = 0;
        if(nums.length < 3) return ans;
        for(int first = 0; first < nums.length; first++) {
            int head = first + 1;
            int tail = nums.length - 1;
            while(head < tail) {
                int sum3 = nums[head] + nums[tail] + nums[first];
                int d = Math.abs(sum3 - target);
                if(d == 0) return target;
                if(d < diff) {
                    diff = d;
                    ans = sum3;
                }
                if(sum3 > target) tail--;
                if(sum3 < target) head++;
            }
            // skip the same elements
            while(first < nums.length-1 && nums[first+1] == nums[first])
                first++;
        }
        return ans;
    }
}

Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = sum(nums[:3])
        for i in range(len(nums)-2):
            k = len(nums)-1
            j = i + 1
            while j < k:
                close_sum = nums[i] + nums[j] + nums[k]
                if close_sum == target:
                    return close_sum
                if abs(close_sum - target) < abs(ans - target):
                    ans = close_sum

                if close_sum < target:
                    j += 1
                elif close_sum > target:
                    k -= 1
                else:
                    break
        return ans

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← Learn from Source Code (an Effec... How to Learn Linux? (from Zero t... →