[LeetCode] 016. 3Sum Closest

Mar. 29, 2019 - Friday

Algorithm

leetcode

python

Problem
Approach 1: $O(n^2)$
- Idea
- Solution
- Complexity

Problem

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

Approach 1: $O(n^2)$

Idea

Similar idead to 015. 3Sum:

First, sorted the number list;
Second, loop the number $i$ as the smallest number in the triple nums;
Third, use another two pointer $j$ and $k$ to narrow the differnce between the the sum of the triple nums and the target.

Solution

    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        dist = sum(nums[:3])
        print(dist)
        for i in range(len(nums)-2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s == target:
                    return s
                elif s < target:
                    if abs(s - target) < abs(dist - target):
                        dist = s
                    j += 1
                else:
                    if abs(s - target) < abs(dist - target):
                        dist = s
                    k -= 1
        return dist

Complexity

Time: $O(n^2)$
Space: $O(1)$