leetcode--16--最接近的三数之和

题目：
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

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

链接：https://leetcode-cn.com/problems/3sum-closest

思路：
1、本题和3数之和的进阶版。首先将nums数组排序，然后采用3个指针，头指针来对数组进行遍历，左指针指向头指针下一个，右指针指向数组最右侧，根据3个指针的元素之和与target之间的diff查来判断左右指针的移动方向。此外需要一个flag来记录3个指针的元素之和和target的大小关系

Python代码：

import sys

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        ret = sys.maxint 
        
        for index, item in enumerate(nums):
            if index>0 and nums[index]==nums[index-1]:
                continue
            left = index+1
            right = len(nums)-1
            while left<right:
                threeSum = item+nums[left]+nums[right]
                if abs(threeSum-target) < abs(ret-target):
                    ret = threeSum
                if item+nums[left]+nums[right]==target:
                    return target
                elif item+nums[left]+nums[right]>target:
                    right -= 1
                else:
                    left += 1
        return ret

C++代码：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        long int ret = INT_MAX;
        int size = nums.size();
        sort(nums.begin(), nums.end());

        for (int i=0; i<size; i++){
            int item = nums[i];
            int left = i+1;
            int right = size-1;
            while(left<right){
                int threeSum = item + nums[left] + nums[right];
                if (abs(threeSum-target)<abs(ret-target)){
                    ret = threeSum;
                }
                if(threeSum==target) return threeSum;
                else if (threeSum-target>0) {
                    right -= 1;
                }else{
                    left += 1;
                }
            }
        }
        return ret;
    }
};