3Sum Closest

Source

• lintcode: 3Sum Closest ``` Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.

Example For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Note You may assume that each input would have exactly one solution.

Challenge O(n^2) time, O(1) extra space

## Python

```python
class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @param target : An integer
    @return : return the sum of the three integers, the sum closest target.
    """
    def threeSumClosest(self, nums, target):
        # write your code here
        if nums is None or len(nums)<3:
            return None

        nums.sort()
        result = nums[0]+nums[1]+nums[2]

        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            left=i+1
            right=len(nums)-1

            while left<right:
                if right<len(nums)-1 and nums[right]==nums[right+1]:
                    right-=1
                    continue
                res = nums[i]+nums[left]+nums[right]
                if res==target:
                    return res
                elif res<target:
                    left+=1
                else:
                    right-=1
                result = result if abs(result-target)<abs(res-target) else res
        return result