LeetCode 16. 3Sum Closest

Description

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

Constraints:

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

Explanation

3Sum Closest is a follow-up question for two sum.

For 3Sum Closest, we are going to find the closest sum to the target. The closest sum could be the target itself or a number close to the target.

1. First, we can sort the array into ascending order.
2. Second, we declare an integer variable called closetSum. That’s the final value we are going to return.
3. Then we can iterate all the numbers in the array. Whenever visiting a number, we should find two numbers in the rest of array which adds the number closet to target. Once iteration finished, we get the result.

Java Solution

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

Python Solution

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        three_sum_closest = sys.maxsize
        
        nums = sorted(nums)
                
        for i, num in enumerate(nums):        
            l = i + 1
            r = len(nums) - 1
                        
            while l < r:       
                local_sum = nums[i] + nums[l] + nums[r]
                if abs(local_sum - target)  < abs(three_sum_closest - target):
                    three_sum_closest = local_sum
                
                if local_sum <= target:
                    l += 1
                else:
                    r -= 1
        
        return three_sum_closest

        

• Time Complexity: O(Nlog(N))
• Space Complexity: O(1)