3Sum Closest

3Sum Closest Add to List QuestionEditorial Solution My Submissions
Total Accepted: 109596
Total Submissions: 358454
Difficulty: Medium
Contributors: Admin
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. You may assume that each input would have exactly one solution.

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

和3sum差不多，使用双指针，唯一得区别是每次指针移动判断得是和目标之间得距离得绝对值。

    class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size()==0)
        return 0;
        int res=0;
        int interval=0;
        sort(nums.begin(),nums.end());
        res=nums[0]+nums[1]+nums[nums.size()-1];
        interval=abs(target-res);
        for(int i=0;i<nums.size()-2;i++)
        {
          int j=i+1,k=nums.size()-1;
            while(j!=k)
        {
            if(nums[i]+nums[j]+nums[k]==target)
              return target;
            else if(nums[i]+nums[j]+nums[k]<target)
            {
             if(target-nums[i]-nums[j]-nums[k]<interval)
            {interval=abs(target-nums[i]-nums[j]-nums[k]);
            res=nums[i]+nums[j]+nums[k];
            }
          j++; }
            else if(nums[i]+nums[j]+nums[k]>target)
            {
            if(nums[i]+nums[j]+nums[k]-target<interval)
            {interval=abs(nums[i]+nums[j]+nums[k]-target);
            res=nums[i]+nums[j]+nums[k];
          } k--;}
        }
        }
        return res;
    }
};