Leetcode 16. 3Sum Closest

3Sum Closest.

This problem can be solved by search all possible 3-tuple. But this will end up with a O(n3) complexity.

A smarter way is to search through one of the number and then use a O(n) 2 SUM algorithm to find the rest two. As as result, this problem can be solved with a complexity of O(n2).

There two O(n) 2 Sum algorithms as far as I know, one is to utilize the O(1) read characteristic of a Hash table, but this problem, we are not looking for the exactly match, so this one may not work well. The other algorithm is to have left and right pointer pointing to a temporary 2-tuple. Initially they should point to the head and tail of the sorted number set. The if the sum is larger than the target, we move the right pointer a position left, and if the sum is smaller than the target, we move the left pointer a position right, until the left and right pointer meet each other.

The reason why moving two pointers linearly will cover the whole solution set is if the sum is larger than the target, then the current left has been the best fit for the current right number, which in other words, there is no better other number to form a better solution 2-tuple with the current right. So we skip checking the sum for other numbers and move the right a position left.

To look for the closest sum, every time we have a sum, we can just compare it with the current optimal.

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        int closest = 0;
        for(int i = 0; i < 3 && i < nums.Length; i++){
            closest += nums[i];
        }
        if(nums.Length <= 3) return closest;
        Array.Sort(nums);
        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) < Math.Abs(closest - target)) closest = sum;
                if(sum > target) right -= 1;
                else { left += 1;}
            }
        }
        return closest;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *