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. 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).
C++:
01 bool compare(int i,int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     int threeSumClosest(vector<int> &num, int target) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         int n=num.size();
11         if(n<3) return 0;
12         sort(num.begin(),num.end(),compare);
13         int result=num[0]+num[1]+num[2];
14         int dist=resulttarget;
15         dist=dist<0?-dist:dist;
16         for(int i=0;i<n;i++)
17         {
18             int j=i+1;
19             int k=n1;
20             while(j<k)
21             {
22                 int d=num[i]+num[j]+num[k]target;
23                 if(d==0)    return target;
24                 if(d<0)
25                 {
26                     if(d<dist)
27                     {
28                         dist=-d;
29                         result=d+target;
30                     }
31                     j++;
32                 }
33                 else
34                 {
35                     if(d<dist)
36                     {
37                         dist=d;
38                         result=d+target;
39                     }
40                     k;
41                 }
42             }
43         }
44         return result;
45     }
46 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s